HDU 4496-D-CIty(並列調査セット)

D-City
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65535/65535 K (Java/Others) Total Submission(s): 6470 Accepted Submission(s): 2213
Problem Description
Luxer is a really bad guy. He destroys everything he met. One day Luxer went to D-city. D-city has N D-points and M D-lines. Each D-line connects exactly two D-points. Luxer will destroy all the D-lines. The mayor of D-city wants to know how many connected blocks of D-city left after Luxer destroying the first K D-lines in the input. Two points are in the same connected blocks if and only if they connect to each other directly or indirectly.
Input
First line of the input contains two integers N and M. Then following M lines each containing 2 space-separated integers u and v, which denotes an D-line. Constraints: 0 < N <= 10000 0 < M <= 100000 0 <= u, v < N.
Output
Output M lines, the ith line is the answer after deleting the first i edges in the input.
Sample Input
5 10 0 1 1 2 1 3 1 4 0 2 2 3 0 4 0 3 3 4 2 4
Sample Output
1 1 1 2 2 2 2 3 4 5
Hint
The graph given in sample input is a complete graph, that each pair of vertex has an edge connecting them, so there’s only 1 connected block at first. The first 3 lines of output are 1s because after deleting the first 3 edges of the graph, all vertexes still connected together. But after deleting the first 4 edges of the graph, vertex 1 will be disconnected with other vertex, and it became an independent connected block. Continue deleting edges the disconnected blocks increased and finally it will became the number of vertex, so the last output should always be N.
問題の説明ルクセ(Luxer)は本当に悪人だ.彼は出会ったすべてを破壊した.ある日、ルクセイはD-cityに行きました.D-cityにはN個のD点とM本のD線があります.各D線はちょうど2つのD点を接続している.ルクソはすべてのD線を破棄する.D-cityの市長はLuxerが入力中の前K本D-lineを破棄した後、D-cityの接続ブロックがどれだけ残っているか知りたい.2つの点が直接または間接的に相互に接続されている場合にのみ、それらは同じ接続ブロックに存在する.
入力値入力の最初の行には、2つの整数NおよびMが含まれる.次のM行は、それぞれ、スペースで区切られた2つの整数uおよびvを含み、D行を表す.範囲:0 0 0<=u,v
出力量はM行を出力し,i行目は入力中の前のi辺を削除した後の答えである.
サンプル入力5 10 0 1 1 2 1 3 1 4 0 2 3 4 4 4
サンプル出力1 1 1 2 2 2 3 4 5
ヒント:サンプル入力で与えられた図は完全な図で、各頂点にはエッジが接続されているため、最初は接続されているブロックが1つしかありません.図の最初の3つのエッジを削除した後も、すべての頂点が接続されているため、出力の最初の3つの動作1です.ただし、図の最初の4つのエッジを削除すると、頂点1は他の頂点と接続されず、独立した接続ブロックとなります.エッジを削除し続け、接続を解除したブロックが増加し、最後に頂点数になるため、最後の出力は常にNになる必要があります.
タイトルリンク
N個の都市と削除するM個の辺を与えて、現在このN個の都市はM個の道を通じて互いにつながっている(与えられた図は必ずしも連通しているとは限らない)ことを意味して、それから出力して順次第i条のいくつかの連通している区域を取り外します.问题の考え方:この问题は考査して集を调べて、以前と违ってこれは私达が逆さまに保存することができて、最初はすべて互いにつながっていないので、それから最后の道から上へつながって、m回を出力するので、私达は1つのansの配列を设置して、ansに最初からnを待たせて、私达は逆さまにつながっているので、最初はきっと互いにつながっていないで、それから1回続けて判断して、父ノードが異なる場合は連通し、ans–、父ノードが同じ場合は連通し続け、最後にansの値を順次出力すればよい.ACコード:

#include 
#include 
#include 
#include 
using namespace std;
const int _max=1e5+50;
struct node {int a,b;};
int f[_max],s[_max];
node ai[_max];
int main()
{
	int n,m;
	int getf(int);
	while(~scanf("%d%d",&n,&m))
	{ 
	  int a,b,cnt=1;;
	  for(int i=1;i<=m;i++)
	    scanf("%d%d",&ai[i].a,&ai[i].b);
	  for(int i=0;i<n;i++)
	      f[i]=i;//      
	  int sum=n;	  
	  for(int i=m;i>0;i--)
	  {
		s[i]=sum;
		int x=getf(ai[i].a);
		int y=getf(ai[i].b);
		if(x!=y)//          
		{
			sum--;
			f[y]=x;
		}
	  }
	  for(int i=1;i<=m;i++)
	    printf("%d
",s[i]);
	}
	//system("pause");
	return 0;
}
int getf(int v)//      
{
	if(f[v]==v)
	  return v;
	else
	{
		f[v]=getf(f[v]);
		return f[v];
	}  
}