文章

211

粉丝

0

获赞

1008

访问

34.0k

头像
连通图 题解:
P1367 吉林大学机试题
发布于2026年3月2日 14:41
阅读数 86

#include<bits/stdc++.h>
using namespace std;

vector<int> g[1005];
bool vis[1005];
void dfs(int x) {
    vis[x] = true;
    for (int y : g[x]) {
        if (!vis[y]) 
			dfs(y);
    }
}
int main() {
    int n, m;
    while (cin >> n >> m) {
        for (int i = 1; i <= n; i++) // 初始化
			g[i].clear();
        memset(vis, 0, sizeof(vis));	
        for (int i = 0; i < m; i++) {// 读入边
            int x, y;
            cin >> x >> y;
            g[x].push_back(y);
            g[y].push_back(x);
        }
        if (n == 0 || n == 1) {	// 特殊情况处理
            cout << "YES\n";
            continue;
        }	
        int cnt = 0;// 计算连通分量
        for (int i = 1; i <= n; i++) {
            if (!vis[i]) {
                cnt++;
                dfs(i);
            }
        }
	cout << (cnt == 1 ? "YES" : "NO") << endl;
    }
    return 0;
}

 

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发