sdut 2819 比赛排名(边表 拓扑排序)

题目:http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=2819

 #include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
const int maxn = +;
int t, head[maxn], cnt[maxn], a[maxn]; struct node
{
int u, v, next;
} g[maxn];
void init()
{
t = ;
memset(head, -, sizeof(head));
memset(cnt, , sizeof(cnt));
}
void add(int u, int v)
{
g[t].u = u;
g[t].v = v;
g[t].next = head[u];
head[u] = t;
t++;
}
void topo(int u)
{
int i;
for(i = head[u]; i != -; i = g[i].next)
cnt[g[i].v]--;
}
int main()
{
int n, m, p1, p2, f;
int i, j, x;
while(~scanf("%d%d", &n, &m))
{
f = ;
x = ;
init();
while(m--)
{
scanf("%d%d", &p1, &p2);
add(p1, p2); //有向边
cnt[p2]++;
}
for(i = ; i <= n; i++)
{
for(j = ; j <= n; j++)
{
if(cnt[j]==)
{
cnt[j] = -;
a[x++] = j;
topo(j); //拓扑排序,去掉入度
break;
}
}
if(j == n+) //如果没有入度为0的,说明不符合条件
{
f = ;
break;
}
}
if(f)
printf("-1\n");
else
{
for(i = ; i <= n; i++)
if(i==n)
printf("%d\n", a[i]);
else
printf("%d ", a[i]);
}
}
return ;
}
上一篇:Reveal-Plugin-for-Xcode 自动结合 Reveal 进行 UI 分析


下一篇:IDEA破解 Intellij IDEA license server 激活(可用)