hdu2120 Ice_cream's world I(検索ループの個数を調べる)
Ice_cream's world I
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 887 Accepted Submission(s): 517
Problem Description
ice_cream's world is a rich country, it has many fertile lands. Today, the queen of ice_cream wants award land to diligent ACMers. So there are some watchtowers are set up, and wall between watchtowers be build, in order to partition the ice_cream’s world. But how many ACMers at most can be awarded by the queen is a big problem. One wall-surrounded land must be given to only one ACMer and no walls are crossed, if you can help the queen solve this problem, you will be get a land.
Input
In the case, first two integers N, M (N<=1000, M<=10000) is represent the number of watchtower and the number of wall. The watchtower numbered from 0 to N-1. Next following M lines, every line contain two integers A, B mean between A and B has a wall(A and B are distinct). Terminate by end of file.
Output
Output the maximum number of ACMers who will be awarded.
One answer one line.
Sample Input
Sample Output
Author
Wiskey
Source
HDU 2007-10 Programming Contest_WarmUp
Recommend
ウイスキー | We have carefully selected several similar problems for you: 2122 2118 2119 2121 2117
Statistic | Submit | Discuss | Note
この問題の意味は1つの図の中にいくつかの環があることを探すことです.
私のすべての知識があまりにも死んだせいだ.ああ、最初は思いもよらなかった.のこのような問題をもういくつかほしい.
拾わせてください.の
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 887 Accepted Submission(s): 517
Problem Description
ice_cream's world is a rich country, it has many fertile lands. Today, the queen of ice_cream wants award land to diligent ACMers. So there are some watchtowers are set up, and wall between watchtowers be build, in order to partition the ice_cream’s world. But how many ACMers at most can be awarded by the queen is a big problem. One wall-surrounded land must be given to only one ACMer and no walls are crossed, if you can help the queen solve this problem, you will be get a land.
Input
In the case, first two integers N, M (N<=1000, M<=10000) is represent the number of watchtower and the number of wall. The watchtower numbered from 0 to N-1. Next following M lines, every line contain two integers A, B mean between A and B has a wall(A and B are distinct). Terminate by end of file.
Output
Output the maximum number of ACMers who will be awarded.
One answer one line.
Sample Input
8 10
0 1
1 2
1 3
2 4
3 4
0 5
5 6
6 7
3 6
4 7
Sample Output
3
Author
Wiskey
Source
HDU 2007-10 Programming Contest_WarmUp
Recommend
ウイスキー | We have carefully selected several similar problems for you: 2122 2118 2119 2121 2117
Statistic | Submit | Discuss | Note
この問題の意味は1つの図の中にいくつかの環があることを探すことです.
私のすべての知識があまりにも死んだせいだ.ああ、最初は思いもよらなかった.のこのような問題をもういくつかほしい.
拾わせてください.の
#include <stdio.h>
int fa[1005];
int find(int x)
{
if(fa[x]!=x) fa[x]=find(fa[x]);
return fa[x];
}
bool comb(int a,int b)
{
a=find(a);
b=find(b);
if(a==b)//
return true;
else
{
fa[a]=b;
return false;
}
}
void init(int n)
{
for(int i=0;i<n;i++)
fa[i]=i;
}
int main()
{
int n,k;
while(scanf("%d %d",&n,&k)!=EOF)
{
init(n);
int sum=0;
for(int i=0;i<k;i++)
{
int a,b;
scanf("%d %d",&a,&b);
if(comb(a,b))
sum++;
}
printf("%d
",sum);
}
return 0;
}