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;
}

Download