﻿HDU 1232 畅通工程(并查集)-Ocrosoft

# 畅通工程

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 46553    Accepted Submission(s): 24765

Problem Description

Input

3 3
1 2
1 2
2 1

Output

Sample Input
```

4 2
1 3
4 3
3 3
1 2
1 3
2 3
5 2
1 2
3 5
999 0
0

```

Sample Output
```

1
0
2
998

Hint

Huge input, scanf is recommended.

```

Solution
```
#include <set>
#include <map>
#include <cmath>
#include <list>
#include <stack>
#include <queue>
#include <ctime>
#include <string>
#include <cstdio>
#include <vector>
#include <cctype>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define ms(a) memset(a,0,sizeof(a))
#define msp memset(mp,0,sizeof(mp));
#define msv memset(vis,0,sizeof(vis));
using namespace std;
int n,m;
int father[10001];
int Find(int x)
{
if(father[x]!=x)x=Find(father[x]);
return father[x];
}
void Union(int x,int y)
{
//int t1=Find(x);
//int t2=Find(y);
//father[t1]=t2;
father[x]=y;
}
int main()
{
while(cin>>n&&n)
{
cin>>m;
for(int i=1;i<=n;i++)father[i]=i;
for(int i=0;i<m;i++)
{
int u,v;
cin>>u>>v;
int fx=Find(u),fy=Find(v);
Union(fx,fy);
}
int ans=0;
for(int i=1;i<=n;i++)
if(Find(i)==i)ans++;
printf("%d\n",ans-1);
}
return 0;
}

```