172. eXam
time limit per test: 0.5 sec.
memory limit per test: 4096 KB
memory limit per test: 4096 KB
input: standard
output: standard
output: standard
In Russia school pupils must do some exams before leaving school. Among others, they must do two "selective" exams. This means that school provides a list of available subjects; each pupil selects two different subjects from this
list and is going to do this exams. According to rules, pupil isn't allowed to do both exams at the same day, so the school must schedule the exams, i.e. provide some days when pupils will be able to do exams.
list and is going to do this exams. According to rules, pupil isn't allowed to do both exams at the same day, so the school must schedule the exams, i.e. provide some days when pupils will be able to do exams.
One school does not want to warn teachers too much. They want to schedule all the exams into two days in such way that exams on some subjects are on the first day, and exams on all other (and only on them) are on second. You are to write a program, which will
determine, if it is possible to schedule exams in this way so that all pupils will be able to do all their selected exams.
Input
On the first line of input there are two integers N and M (1<=N<=200, 1<=M<=30000) - the number of available subjects and the number of pupils. Then M lines follows; on i-th of them there are two integers - the numbers of exams, which
were selected by i-th pupil. Exams are numerated from 1 to N.
were selected by i-th pupil. Exams are numerated from 1 to N.
Output
If the solution exists, write on the first line of output only one word "yes". On the second line write the total number of exams, which must be held on first day, and on the third line - the numbers of subjects of this exams. If
there exist several solutions, output any. If no solution exists, write to output only one word "no".
there exist several solutions, output any. If no solution exists, write to output only one word "no".
Sample test(s)
Input
4 4 1 2 3 4 2 4 1 3
Output
yes
2
1 4
2
1 4
| Author: | NNSU#2 team |
| Resource: | Lazurny olympiad in informatics |
| Date: | July-August 2002 |
|
裸裸地二分图染色判定，一直PE了几十次，已经放弃治疗。。有空再改下。。。
/**********************
* author:crazy_石头
* Pro:SGU 172 判定二分图
* algorithm:dfs
* Time:31ms
* Judge Status:PE!!
***********************/
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <vector>
using namespace std;
#define rep(i,h,n) for(int i=(h);i<=(n);i++)
#define ms(a,b) memset((a),(b),sizeof(a))
#define eps 1e-6
#define INF 1<<29
#define LL __int64
const int maxn=200+5;
const int maxm=200+10;
vector<int> v;
/****************************************
条件：
1、不存在环
2、图是连通图
3、双向图
思路：
任意取一个点进行染色，如果发现要涂某一块时这个块已经被涂了色，并且与我们要使用的颜色不同的话，就说明这个图不能被染成BICOLORABLE的。
（1）如果没有染色，将它染色，并将它周围的点变成相反色。
（2）如果已经染色，判断是否与现在染色的点的颜色相同，相同，则退出，否则继续。
*****************************************/
int map[maxn][maxn];
int vis[maxn];
int color[maxn];
int n,m;
inline int dfs(int u)
{
for(int i=1;i<=n;i++)
if(map[u][i])
{
if(!vis[i])
{
vis[i]=1;
color[i]=!color[u];
dfs(i);
}
else if(color[i]==color[u])
{
puts("no");
return 0;
}
}
return 1;
}
int main()
{
memset(map,0,sizeof(map));
memset(vis,0,sizeof(vis));
scanf("%d%d",&n,&m);
while(m--)
{
int a,b;
scanf("%d%d",&a,&b);
map[a][b]=map[b][a]=1;
}
color[1]=1;
vis[1]=1;
int index;
rep(i,1,n)
{
if(!vis[i])
{
index=i;
break;
}
}
if(dfs(index))
puts("yes");
rep(i,1,n)
if(color[i])v.push_back(i);
cout<<v.size()<<endl;
cout<<v[0];
for(int i=1;i<v.size();i++)
cout<<" "<<v[i];
cout<<endl;
return 0;
}
附上大牛的AC Code：
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
#define N 210
int n,m;
bool map[N][N],visit[N],col[N];
void init()
{
scanf("%d%d",&n,&m);
for (int i=1;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
map[x][y]=map[y][x]=true;
}
for (int i=1;i<=n;i++) col[i]=-1;
return ;
}
void DFS(int x,int co)
{
visit[x]=true;
col[x]=co;
for (int i=1;i<=n;i++)
if (map[x][i])
if (!visit[i]) DFS(i,co^1);
else
if (col[i]==col[x])
{
puts("no");
exit(0);
}
return ;
}
int main()
{
init();
for (int i=1;i<=n;i++)
if (!visit[i])
DFS(i,0);
puts("yes");
int CC=0,tmp=0;
for (int i=1;i<=n;i++)
if (!col[i])
CC++;
printf("%d\n",CC);
for (int i=1;i<=n;i++)
if (!col[i])
{
tmp++;
if (tmp==CC) printf("%d\n",i);
else printf("%d ",i);
}
return 0;
}
好弱。。T_T