sdutacm-大家快来A水题

大家快来A水题

Time Limit: 1000MS MemoryLimit: 65536KB

SubmitStatistic

PRoblemDescription

海上有N(1<= N <=2000)个岛，编号从1到N,同一部落的岛屿之间有直接或间接的路相连，不同部落之间无路可通。现在给出M(1<= M <= N*(N-1)/2)条路。问这片海域上共有多少部落。

Input

 多组输入。每组第一行输入N，M。接下来M行每行，每行两个整数u,v代表岛u与v之间有一条路。

Output

 每组数据输出一个整数，代表部落数。

ExampleInput

3 1

1 2

3 2

1 2

1 3

ExampleOutput

2

1

Hint

Author

#include <iostream>#include<bits/stdc++.h>using namespace std;int f[3000]={0},n,m,k,sum;int getf(int v){    if(f[v]==v)    {        return v;    }    else    {        f[v] = getf(f[v]);        return f[v];    }}void amerge(int l,int r){    int t1,t2;    t1 = getf(l);    t2 = getf(r);    if(t1!=t2)    {        f[t2] = t1;    }    return ;}int main(){    int x,y,i;    while(~scanf("%d%d",&n,&m))    {        for(i=1;i<=n;i++)        {            f[i] = i;        }        for(i=1;i<=m;i++)        {            scanf("%d%d",&x,&y);            amerge(x,y);        }        sum = 0;        for(i = 1;i<=n;i++)        {            if(f[i]==i)            {            sum++;            }        }        printf("%d/n",sum);    }    return 0;}/***************************************************User name: jk160505徐红博Result: AcceptedTake time: 12msTake Memory: 168KBSubmit time: 2017-02-17 10:23:54****************************************************/