小希的迷宮
[cpp]
// File Name: hdu1272.cpp
// Author: rudolf
// Created Time: 2013年04月27日 星期六 13時32分01秒
#include<vector>
#include<list>
#include<map>
#include<set>
#include<deque>
#include<stack>
#include<bitset>
#include<algorithm>
#include<functional>
#include<numeric>
#include<utility>
#include<sstream>
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<ctime>
using namespace std;
const int maxn=100005;
int fa[maxn],hav[maxn];
int flag;
int find( int x )
{
// return fa[ x ] = x == fa[ x ] ? x :find( fa[ x ] );
while( x != fa[ x ])
x = fa[ x ];
return x;
}
void merge( int x1 ,int x2 )
{
int x = find( x1 );
int y = find( x2 );
if( x != y )
fa[ x ] = y;
else
flag = 0;//同父節點，成環
}
int main()
{
int i,m,n;
while(cin>>m>>n)
{
if( m == -1 && n == -1 )
break;
if( m==0 && n==0 )
{
cout<<"Yes"<<endl;
continue;
}
for( i = 1; i < maxn; i++ )
{
fa[ i ] = i;
hav[i]=0;
}
hav[ m ] = hav[ n ] = 1;
flag = 1;
merge( m , n );
while( cin >> m >> n )
{
if( m == 0 && n == 0)
break;
merge( m , n );
hav[ m ] = hav[ n ] = 1;
}
int ans = 0;
for( i = 1;i < maxn; i++)
{
if( hav[ i ] && fa[ i ] == i )//判斷根節點k數目
ans ++;
if( ans > 1 )
flag=0;
}
if( flag )
cout<<"Yes"<<endl;//這裡也坑爹，用PUTS輸出和下面一樣的錯誤
else
cout<<"No"<<endl;
}
return 0;
}
// File Name: hdu1272.cpp
// Author: rudolf
// Created Time: 2013年04月27日 星期六 13時32分01秒
#include<vector>
#include<list>
#include<map>
#include<set>
#include<deque>
#include<stack>
#include<bitset>
#include<algorithm>
#include<functional>
#include<numeric>
#include<utility>
#include<sstream>
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<ctime>
using namespace std;
const int maxn=100005;
int fa[maxn],hav[maxn];
int flag;
int find( int x )
{
// return fa[ x ] = x == fa[ x ] ? x :find( fa[ x ] );
while( x != fa[ x ])
x = fa[ x ];
return x;
}
void merge( int x1 ,int x2 )
{
int x = find( x1 );
int y = find( x2 );
if( x != y )
fa[ x ] = y;
else
flag = 0;//同父節點，成環
}
int main()
{
int i,m,n;
while(cin>>m>>n)
{
if( m == -1 && n == -1 )
break;
if( m==0 && n==0 )
{
cout<<"Yes"<<endl;
continue;
}
for( i = 1; i < maxn; i++ )
{
fa[ i ] = i;
hav[i]=0;
}
hav[ m ] = hav[ n ] = 1;
flag = 1;
merge( m , n );
while( cin >> m >> n )
{
if( m == 0 && n == 0)
break;
merge( m , n );
hav[ m ] = hav[ n ] = 1;
}
int ans = 0;
for( i = 1;i < maxn; i++)
{
if( hav[ i ] && fa[ i ] == i )//判斷根節點k數目
ans ++;
if( ans > 1 )
flag=0;
}
if( flag )
cout<<"Yes"<<endl;//這裡也坑爹，用PUTS輸出和下面一樣的錯誤
else
cout<<"No"<<endl;
}
return 0;
}
這個是下面的代碼提交，深表無語。。。。。。。。。。。。。。。。。。。。。。。。。
[cpp]
// File Name: hdu1272.cpp
// Author: rudolf
// Created Time: 2013年04月27日 星期六 13時32分01秒
#include<vector>
#include<list>
#include<map>
#include<set>
#include<deque>
#include<stack>
#include<bitset>
#include<algorithm>
#include<functional>
#include<numeric>
#include<utility>
#include<sstream>
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<ctime>
using namespace std;
const int maxn=100005;
int fa[maxn],hav[maxn];
int f;
int find( int x )
{
return fa[ x ] = x == fa[ x ] ? x :find( fa[ x ] );
}
void merge( int x1 ,int x2 )
{
int x = find( x1 );
int y = find( x2 );
if( x != y )
fa[ x ] = y;
else
if( x1 != x2 )//防止(1 1) 且判斷兩點之間是否只有一條通路
f = 1;
}
int main()
{
int max;
int m,n;
while( scanf( "%d%d" ,& m ,& n ) && m + n != -2 )
{
int t=0;
memset( hav , 0 , sizeof ( hav ) );
for( int i = 0; i <= maxn; i++ )
fa[ i ] = i;
//int t,max;
f = max = 0;
hav[ n ] = hav[ m ] = 1;
merge(m,n);
max = n > m ? n : m;
//int c;
while( ( m | n ) && ( scanf( "%d%d" ,& m, &n ), m | n ) )//當n和m均為0時，不執行，在輸入前面和輸入數據後面均進行判斷
{
merge( m , n );
t=hav[ m ] = hav[ n ] = 1;
int c = n > m ? n : m;
max = c > max? c : max;
}
int c = 0;
if( !t )//防止惡心數據，當一開始就輸入0 0時，特殊情況
{
printf( "Yes\n" );
continue;
}
//int ans = 0;
for( int i = 0; i <= max; i++)//看有沒有全部連通
if( hav[ i ] )//判斷是否有這條路
if( fa[ i ] == i )
++c;
if( c != 1 )
f=1;
if( !f )
puts( "Yes" );
else
puts( "No" );
}
return 0;
}
// File Name: hdu1272.cpp
// Author: rudolf
// Created Time: 2013年04月27日 星期六 13時32分01秒
#include<vector>
#include<list>
#include<map>
#include<set>
#include<deque>
#include<stack>
#include<bitset>
#include<algorithm>
#include<functional>
#include<numeric>
#include<utility>
#include<sstream>
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<ctime>
using namespace std;
const int maxn=100005;
int fa[maxn],hav[maxn];
int f;
int find( int x )
{
return fa[ x ] = x == fa[ x ] ? x :find( fa[ x ] );
}
void merge( int x1 ,int x2 )
{
int x = find( x1 );
int y = find( x2 );
if( x != y )
fa[ x ] = y;
else
if( x1 != x2 )//防止(1 1) 且判斷兩點之間是否只有一條通路
f = 1;
}
int main()
{
int max;
int m,n;
while( scanf( "%d%d" ,& m ,& n ) && m + n != -2 )
{
int t=0;
memset( hav , 0 , sizeof ( hav ) );
for( int i = 0; i <= maxn; i++ )
fa[ i ] = i;
//int t,max;
f = max = 0;
hav[ n ] = hav[ m ] = 1;
merge(m,n);
max = n > m ? n : m;
//int c;
while( ( m | n ) && ( scanf( "%d%d" ,& m, &n ), m | n ) )//當n和m均為0時，不執行，在輸入前面和輸入數據後面均進行判斷
{
merge( m , n );
t=hav[ m ] = hav[ n ] = 1;
int c = n > m ? n : m;
max = c > max? c : max;
}
int c = 0;
if( !t )//防止惡心數據，當一開始就輸入0 0時，特殊情況
{
printf( "Yes\n" );
continue;
}
//int ans = 0;
for( int i = 0; i <= max; i++)//看有沒有全部連通
if( hav[ i ] )//判斷是否有這條路
if( fa[ i ] == i )
++c;
if( c != 1 )
f=1;
if( !f )
puts( "Yes" );
else
puts( "No" );
}
return 0;
}
