codevs 2833 奇怪的梦境

拓扑排序之即可。

面对重边：新加vis数组。

求不能确定的顺序：cnt，每次入队-1即可。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define maxv 10005
#define maxe 25005
using namespace std;
int n,m,g[maxv],inq[maxv],cnt=0,nume=0,x,y;
bool vis[maxv];
struct edge
{
int v,nxt;
}e[maxe];
void addedge(int uu,int vv)
{
e[++nume].v=vv;
e[nume].nxt=g[uu];
g[uu]=nume;
}
void topu()
{
queue <int> q;
for (int i=1;i<=n;i++)
if ((inq[i]==0) && (vis[i]==true))
{
q.push(i);
cnt--;
}
while (!q.empty())
{
int head=q.front();
q.pop();
for (int i=g[head];i;i=e[i].nxt)
{
int v=e[i].v;
inq[v]--;
if (inq[v]==0)
{
cnt--;
q.push(v);
}
}
}
}
int main()
{
memset(vis,false,sizeof(vis));
memset(g,0,sizeof(g));
memset(inq,0,sizeof(inq));
scanf("%d%d",&n,&m);
for (int i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
if (vis[x]==false) {cnt++;vis[x]=true;}
if (vis[y]==false) {cnt++;vis[y]=true;}
addedge(x,y);
inq[y]++;
}
topu();
if (cnt==0) printf("o(n_n)o\n");
else
{
printf("T_T\n");
printf("%d\n",cnt);
}
return 0;
}

codevs 2833 奇怪的梦境

原文：http://www.cnblogs.com/ziliuziliu/p/5061424.html