NC50411. 和平委员会
描述
输入描述
第一行有两个非负整数n和m。他们各自表示：党派的数量n和不友好的代表对m。接下来m行，每行为一对整数a,b，表示代表a,b互相厌恶。
输出描述
如果不能创立委员会，则输出信息NIE。若能够成立，则输出包括n个从区间1到2n选出的整数，按升序写出，每行一个，这些数字为委员会中代表的编号。
如果委员会能以多种方法形成，程序可以只输出它们的某一个。
示例1
输入:
3 2 1 3 2 4
输出:
1 4 5
C++11(clang++ 3.9) 解法, 执行用时: 13ms, 内存消耗: 1768K, 提交时间: 2020-05-28 11:00:05
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int n,m;
int dfn[16010],low[16010],st[16010],co[16010],tp,col,num;
int head[16010],cnt;
struct edge
{
int nxt,go;
}e[40010];
void add(int u,int v)
{
e[++cnt]=(edge){head[u],v},head[u]=cnt;
}
void tarjan(int x)
{
dfn[x]=low[x]=++num;
st[++tp]=x;
for(int i=head[x];i;i=e[i].nxt)
{
int v=e[i].go;
if(!dfn[v])
{
tarjan(v);
low[x]=min(low[x],low[v]);
}
else if(!co[v])
low[x]=min(low[x],dfn[v]);
}
if(dfn[x]==low[x])
{
co[x]=++col;
while(st[tp]!=x)
{
co[st[tp]]=col;
--tp;
}
--tp;
}
}
int main()
{
scanf("%d %d",&n,&m);
for(int i=1;i<=m;i++)
{
int a,b;
scanf("%d %d",&a,&b);
add(a,b&1?b+1:b-1);
add(b,a&1?a+1:a-1);
}
for(int i=1;i<=n<<1;i++)
if(!dfn[i])
tarjan(i);
for(int i=1;i<=n<<1;i+=2)
if(co[i]==co[i+1])
{
printf("NIE\n");
return 0;
}
for(int i=1;i<=n<<1;i+=2)
printf("%d\n",co[i]<co[i+1]?i:i+1);
return 0;
}