Posted on 2011-11-03 13:57
C小加 阅读(1689)
评论(0) 编辑 收藏 引用 所属分类:
解题报告
BFS，我写的代码有点
冗杂，题很水，不想优化了。。写完后感觉并查集可以过。#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;
}杂。。题比较水，不想优化了。