这一题我想用并查集来着结果超时了,还需要再想想。
题目大意:找出最大的连通分量。
注意:时间为1000MS,内存为102400,内存空间很大,但是用矩阵建立图还是会超内存。用vector,用深搜的方法寻找最大分量。n,m记录最小端点与最大端点,DFS时可以减少端点遍历的时间。
好奇怪,我把n,m定义为min, max时竟然出现编译错误(http://acm.hdu.edu.cn/viewerror.php?rid=9314048 C++编译错误)
(http://acm.hdu.edu.cn/viewerror.php?rid=9314094 G++编译错误)??????有待思考。
#include <iostream> #include <vector> #define MAX 100001 using namespace std; vector <int> graph[MAX]; int visit[MAX]; int n, m, N;//N记录连通分量 void DFS(int n)//深搜 { int i; visit[n] = 1; for (i=0; i<graph[n].size(); i++) if (visit[graph[n][i]]==0) { DFS(graph[n][i]); N++; } } int main() { int num, a, b, i, sum; n=0, m=0; while (cin>>num) { for (i=n; i<=m; i++)//清空vector graph[i].clear(); sum = 1; //sun记录最大连通分量 n = MAX, m = -1; //用n,m缩短端点的遍历范围 while (num--) { cin>>a>>b; graph[a].push_back(b);//建立图 graph[b].push_back(a); if (a<n) n = a; if (b<n) n = b; if (a>m) m = a; if (b>m) m = b; } for (i=0; i<=m; i++) visit[i] = 0;; for (i=n; i<=m; i++) if (visit[i]==0) { N = 1; DFS(i); if (N>sum) sum = N; } cout<<sum<<endl; } return 0; }