POJ1470 Closest Common Ancessors [Tarjan의 LCA]

아주 누드한 모형 문제인데, 단지 Tarjan은 몇 번 더 꺼내서 음미해야 한다.
아주 교묘하네요, tarjan, 아마도 현재의 결점과 그의 아들의 결점의 속박일 거예요.
두 시간 동안, 원인은 이 문제가 다중 데이터이기 때문이다(T를 알려주지 않았는데,scanf!=EOF로 끝을 제어한다). 더 중요한 것은 이것과Codeforces는 다르다. Codeforces의 다중 데이터는 다시 프로그램을 시작하는 것 같아서 프로그램에 0을 쓸 필요가 없다. 그러나 이 문제는 다중 데이터는 EOF로 입력을 제어하는 것이다. 다중 데이터는 한 파일에 한 번에 지기 때문에memset을 사용해야 한다.
btw, 약간의 memset 코드를 더하면 700B 코드가 많아진다...

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
using namespace std;
const int MAXN=1111;
int n;
int in[MAXN];
vector<int> G[MAXN];
int ques[MAXN][MAXN];
bool vis[MAXN];
int fa[MAXN];
int countn[MAXN];
int father(int x)
{
	if(x==fa[x])
		return x;
	return x=father(fa[x]);
}
void dfs(int x)
{
	fa[x]=x;
	for(int i=0;i<G[x].size();i++)
	{
		dfs(G[x][i]);
		fa[G[x][i]]=x;
	}
	vis[x]=true;
	for(int i=1;i<=n;i++)
	{
		if(ques[x][i]&&vis[i])
		{
			countn[father(i)]+=ques[x][i];
		}
	}
}
int main()
{
	#ifndef ONLINE_JUDGE
		freopen("G:/1.txt","r",stdin);
		freopen("G:/2.txt","w",stdout);
	#endif
	while(scanf("%d",&n)==1)
    {
        memset(ques,0,sizeof(ques));
        memset(vis,0,sizeof(vis));
        memset(fa,0,sizeof(fa));
        memset(countn,0,sizeof(countn));
        memset(in,0,sizeof(in));
        for(int i=0;i<MAXN;i++)
        {
            G[i].clear();
        }
        for(int i=1;i<=n;i++)
        {
            int x,ynum;
            scanf("%d:(%d)",&x,&ynum);
            for(int j=1;j<=ynum;j++)
            {
                int y;
                scanf(" %d",&y);
                G[x].push_back(y);
                in[y]++;
                //G[y].push_back(x);
            }
        }
            int quesnum;
            scanf(" %d",&quesnum);
            for(int i=1;i<=quesnum;i++)
            {
                int xx,yy;
                scanf(" (%d %d)",&xx,&yy);
                ques[xx][yy]++;
                ques[yy][xx]++;
            }
            for(int i=1;i<=n;i++)
            {
                if(!in[i])
                {
                    dfs(i);
                    break;
                }
            }
            for(int i=1;i<=n;i++)
            {
                if(countn[i])
                    printf("%d:%d
",i,countn[i]);
            }
    }
    return 0;
}