1080. Map Colouring
Time Limit: 1.0 second
Memory Limit: 16 MB
We consider a geographical map with N countries numbered from 1 to N (0 < N < 99). For every country we know the numbers of other countries which are connected with its border. From every country we can reach to any other one, eventually crossing some borders. Write a program which determines whether it is possible to colour the map only in two colours — red and blue in such a way that if two countries are connected their colours are different. The colour of the first country is red. Your program must output one possible colouring for the other countries, or show, that such colouring is impossible.
Input
On the first line is written the number N. On the following N lines, the i-th line contains the countries to which the i-th country is connected. Every integer on this line is bigger than i, except the last one which is 0 and marks that no more countries are listed for country i. If a line contains 0, that means that the i-th country is not connected to any other country, which number is larger than i.
Output
The output contains exactly one line. If the colouring is possible, this line must contain a list of zeros and ones, without any separators between them. The i-th digit in this sequence is the colour of the i-th country. 0 corresponds to red colour, and one — to blue colour. If a colouring is not possible, output the integer −1.
Sample
| input |
output |
3
2 0
3 0
0
|
010
|
|
DFS:或BFS，或者并查集（不會(huì)用）
這里用的DFS，用一個(gè)標(biāo)記數(shù)組，沒(méi)進(jìn)入一個(gè)聯(lián)通分圖后，標(biāo)記為0（表示一種顏色）與它相連的標(biāo)記為1（另一種顏色），
然后與1相連的在標(biāo)記為0。 這里的標(biāo)記都是對(duì)沒(méi)有標(biāo)記過(guò)的進(jìn)行的，如果是標(biāo)記過(guò)的，就要檢查他們的標(biāo)記是否相同
如果相同則說(shuō)明，他們同色。
//ural 1080
#include<iostream>
using namespace std;
const int MAX=100;
bool adj[MAX][MAX];
int flg[MAX];
int n;
bool isPossible=true;
void input()
{
cin>>n;
int temp;
for(int i=1; i<=n; i++)
{
while(cin>>temp,temp!=0)
{
adj[i][temp]=adj[temp][i]=true;
}
}
}
void dfs(int i)
{
if(isPossible==false)return ;
if(flg[i]==-1)flg[i]=0;
for(int j=1; j<=n; j++)
{
if(adj[i][j])
{
if(flg[j]==-1){ flg[j]=flg[i]==0? 1:0; dfs(j); }
else if(flg[j]==flg[i])isPossible=false;
}
}
}
int main()
{
memset(adj,0,sizeof adj);
input();
for(int i=1; i<=n; i++)
flg[i]=-1;
flg[1]=0;
for(int i=1; i<=n; i++)
dfs(i);
if(isPossible==false)cout<<-1<<endl;
else {
for(int k=1; k<=n; k++)
cout<<flg[k];
cout<<endl;
}
system("pause");
return 0;
}