希ちゃんの迷路
希ちゃんの迷宮
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 11354 Accepted Submission(s): 3367
Problem Description
前回Gardonの迷宮城で希ちゃんは長い間遊んでいましたが(Problem Bを参照)、今でもGardonを行かせる迷宮を設計したいと思っています.しかし彼女は迷路を設計する構想が異なって、まず彼女はすべての通路が双方向に連通しているべきだと思って、つまりもし1つの通路が部屋AとBを連通しているならば、それを通じて部屋Aから部屋Bまで歩くことができて、それを通じて部屋Bから部屋Aまで歩くことができて、難易度を高めるために、小希は任意の2つの部屋があってしかも1つの経路だけが連通していることを望んでいます(振り返る道を歩かない限り).希ちゃんは今彼女の設計図をあなたにあげて、彼女の設計図が彼女の設計構想に合っているかどうかを判断させます.例えば、次の例では、前の2つは条件に合っていますが、最後の2つの方法は5から8に着きます.
Input
0で終わる整数対のリストで、1つのチャネルで接続されている2つの部屋の番号を示す複数のグループのデータを入力します.部屋の番号は少なくとも1で、100000を超えません.2つのグループのデータの間に空の行があります.
ファイル全体が2つの-1で終わります.
Output
入力されたデータのセットごとに出力は1行のみです.迷路が希ちゃんの考えに合っている場合は「Yes」を出力し、そうでない場合は「No」を出力します.
Sample Input
# include int pre[100001]; int num[100001],flag; void make_pre() { for(int i=0;i<=100001;i++) { pre[i]=i; num[i]=0; } } int find(int x) { return x==pre[x]?x:pre[x]=find(pre[x]); } void mergy(int x,int y) { int x1=find(x); int y1=find(y); if(x1!=y1) { pre[x1]=y1; } else flag=0; } int main() { int a,b; while(scanf("%d%d",&a,&b),a!=-1&&b!=-1) { make_pre(); int sum=0; flag=1; while(a!=0&&b!=0) { mergy(a,b); num[a]=num[b]=1; scanf("%d%d",&a,&b); } for(int i=0;i<100001;i++) { if(num[i] && pre[i]==i) sum++; if(sum>1) { flag=0; break; } } if(flag) printf("Yes"); else printf("No"); } } ps:1本の道しかなく、複数の道ではありません.最初は初期化を忘れてWA、初期化が重要です);
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 11354 Accepted Submission(s): 3367
Problem Description
前回Gardonの迷宮城で希ちゃんは長い間遊んでいましたが(Problem Bを参照)、今でもGardonを行かせる迷宮を設計したいと思っています.しかし彼女は迷路を設計する構想が異なって、まず彼女はすべての通路が双方向に連通しているべきだと思って、つまりもし1つの通路が部屋AとBを連通しているならば、それを通じて部屋Aから部屋Bまで歩くことができて、それを通じて部屋Bから部屋Aまで歩くことができて、難易度を高めるために、小希は任意の2つの部屋があってしかも1つの経路だけが連通していることを望んでいます(振り返る道を歩かない限り).希ちゃんは今彼女の設計図をあなたにあげて、彼女の設計図が彼女の設計構想に合っているかどうかを判断させます.例えば、次の例では、前の2つは条件に合っていますが、最後の2つの方法は5から8に着きます.
Input
0で終わる整数対のリストで、1つのチャネルで接続されている2つの部屋の番号を示す複数のグループのデータを入力します.部屋の番号は少なくとも1で、100000を超えません.2つのグループのデータの間に空の行があります.
ファイル全体が2つの-1で終わります.
Output
入力されたデータのセットごとに出力は1行のみです.迷路が希ちゃんの考えに合っている場合は「Yes」を出力し、そうでない場合は「No」を出力します.
Sample Input
6 8 5 3 5 2 6 4
5 6 0 0
8 1 7 3 6 2 8 9 7 5
7 4 7 8 7 6 0 0
3 8 6 8 6 4
5 3 5 6 5 2 0 0
-1 -1
# include int pre[100001]; int num[100001],flag; void make_pre() { for(int i=0;i<=100001;i++) { pre[i]=i; num[i]=0; } } int find(int x) { return x==pre[x]?x:pre[x]=find(pre[x]); } void mergy(int x,int y) { int x1=find(x); int y1=find(y); if(x1!=y1) { pre[x1]=y1; } else flag=0; } int main() { int a,b; while(scanf("%d%d",&a,&b),a!=-1&&b!=-1) { make_pre(); int sum=0; flag=1; while(a!=0&&b!=0) { mergy(a,b); num[a]=num[b]=1; scanf("%d%d",&a,&b); } for(int i=0;i<100001;i++) { if(num[i] && pre[i]==i) sum++; if(sum>1) { flag=0; break; } } if(flag) printf("Yes"); else printf("No"); } } ps:1本の道しかなく、複数の道ではありません.最初は初期化を忘れてWA、初期化が重要です);