NKONEARC - Mạng máy tính
Tác giả: ladpro98
Ngôn ngữ: C++
#include <bits/stdc++.h>
const int N = 2222;
using namespace std;
int low[N], num[N], st[N], lab[N], in[N], out[N];
int n, m, cnt, scc, top;
bool was[N];
vector<int> a[N];
void DFS(int u) {
low[u] = num[u] = ++cnt;
st[++top] = u;
int i, v;
for(i=0; i<a[u].size(); i++) {
v = a[u][i];
if (was[v]) continue;
if (num[v] != 0)
low[u] = min(low[u], num[v]);
else {
DFS(v);
low[u] = min(low[u], low[v]);
}
}
if (num[u] == low[u]) {
scc++;
do {
v = st[top--];
lab[v] = scc;
was[v] = true;
} while (v != u);
}
}
int main()
{
scanf("%d %d\n", &n, &m);
int i, u, v, source = 0, sink = 0, s, t;
for(i=1; i<=m; i++) {
scanf("%d %d\n", &u, &v);
a[u].push_back(v);
}
for(i=1; i<=n; i++)
if (num[i] == 0)
DFS(i);
for(u=1; u<=n; u++)
for(i=0; i<a[u].size(); i++) {
v = a[u][i];
if (lab[u] != lab[v]) {
in[lab[v]]++;
out[lab[u]]++;
}
}
for(i=1; i<=scc; i++) {
if (in[i] == 0) {
source++; s = i;
}
if (out[i] == 0) {
sink++; t = i;
}
}
if (source != 1 || sink != 1) printf("NO");
else {
printf("YES\n");
for(i=1; i<=n; i++) if (lab[i] == s) {s = i; break;}
for(i=1; i<=n; i++) if (lab[i] == t) {t = i; break;}
printf("%d %d", t, s);
}
return 0;
}