Posted on 2011-11-03 13:57
C小加 閱讀(1716)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
解題報(bào)告
BFS，我寫的代碼有點(diǎn)
冗雜，題很水，不想優(yōu)化了。。寫完后感覺并查集可以過。#include <cstring>
#include <queue>
using namespace std;
const int MAXN=103;
int n;
int map[MAXN][MAXN];
int col[MAXN];
queue<int> que;
void Init()
{
memset(map,0,sizeof(map));
memset(col,-1,sizeof(col));
}
void Read()
{
int t;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>t;
while(t)
{
map[i][t]=map[t][i]=1;
cin>>t;
}
}
}
bool BFS(int k)
{
que.push(k);
if(col[k]==-1)
col[k]=0;
while (!que.empty())
{
int f=que.front();
que.pop();
int e=col[f];
for (int i=1;i<=n;i++)
{
if(map[f][i])
{
if(col[i]==-1)
{
que.push(i);
col[i]=(e+1)%2;
}
else if(col[i]==e) return false;
}
}
}
return true;
}
int main()
{
Init();
Read();
int flag=1;
for(int i=1;i<=n;i++)
{
if(!BFS(i))
{
flag=0;
break;
}
}
if(flag)
{
for (int i=1;i<=n;i++)
{
cout<<col[i];
}
cout<<endl;
}
else
{
cout<<-1<<endl;
}
return 0;
}雜。。題比較水，不想優(yōu)化了。