2024拓扑
作者:
Lw1
,
2024-10-18 08:56:32
,
所有人可见
,
阅读 3
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
int n , m;
const int N = 1010;
int g[N][N];
int cnt[N];
bool st[N]; //记录点是否已删除
int f()
{
queue<int> q;
for(int i = 1 ; i <= n ; i ++)
{
for(int j = 1 ; j <= n ; j ++)
{
if(g[i][j] == 1) cnt[j] ++;
}
}
int num = 0;
for(int i = 1 ; i <= n ; i ++)
{
if(cnt[i] == 0) q.push(i) , num ++;
if(num > 1) return 0;
}
while(q.size())
{
if(q.size() > 1) return 0;
int t = q.front();
cout << t << ' ';
q.pop();
for(int j = 1 ; j <= n ; j ++)
{
if(g[t][j] == 1)
{
cnt[j] --;
if(cnt[j] == 0) q.push(j);
}
}
}
// for(int i = 0 ; i < n ; i ++)
// {
// int num = 0;
// int t;
// for(int j = 1 ; j <= n ; j ++)
// {
// if(cnt[j] == 0 && !st[j]) num ++ , t = j;
// }
// if(num > 1) return 0;
// st[t] = true;
// for(int j = 1 ; j <= n ; j ++)
// {
// if(g[t][j] == 1) cnt[j] --;
// }
// }
return 1;
}
int main()
{
cin >> n >> m;
for(int i = 0 ; i < m ; i ++)
{
int a , b;
cin >> a >> b;
g[a][b] = 1;
}
cout << f() << endl;
return 0;
}