最后一道暑假作业了，谁能救救我

问题讨论区 普及段
1

29. 图2-图的连通块个数

题目ID：8253必做题100分

最新提交：

Time Limit Exceeded

0 分

历史最高：

Time Limit Exceeded

0 分

时间限制: 1000ms

空间限制: 131072kB

题目描述

时间：1s 空间：128M

题目描述:

给出一个无向图，要求输出这个图的连通块个数

输入格式:

共 M+1M+1 行。
第一行包含两个正整数 NN 和 MM，表示有 NN 个点，MM 条边。(N,M≤200000)(N,M≤200000)
接下来 MM 行，每行包含两个用空格隔开的正整数 uu 和 vv，表示一条从 uu 到 vv 的无向路径。（注意，可能会有重边和自环）

输出格式:

一个整数表示图的连通块个数

样例1输入:

5 6 1 2 3 4 5 2 5 1 1 5 4 4

样例1输出:

2

下面是我的TLE代码

#include<bits/stdc++.h>
using namespace std;
int m,n,s,vis[100005],ans=0;
vector< vector<int> >node;
void dfs(int k){
	vis[k]=1;
	for(int i=1;i<=node[k].size();i++){
		if(vis[node[k][i]]==0){
			dfs(node[k][i]);
		}
	}
}
int main(){
	cin>>n>>m;
    node.resize(n+1);
	for(int i=1;i<=m;i++){
		int x,y;
		cin>>x>>y;
		node[x].push_back(y);
		node[y].push_back(x);
	}
	for(int i=1;i<=n;i++){
		if(vis[i]==0){
			ans++;
			dfs(1);
		} 
		
	}
	cout<<ans/2;
    return 0;
}

那位大佬能救救我

1 个赞
2

你再dfs里面给vis数组标记的位置应该在判断里面
vis[node[k][i]]=1

1 个赞
3

而且，再主函数里面不能直接进入node动态数组，用判断是不是重复或者自环

1 个赞
4

输出时直接输出ans就可以了
node.resize(n+1);
这个时候就可以去掉

1 个赞
5

for(int i=1;i<=node[k].size();i++)
改成
for(int i=0;i<node[k].size();i++)

1 个赞
6

你在这个循环里应该是从0到SIZE-1

然后你这里要判断重边和自环

1 个赞