NKONEARC - Mạng máy tính

Tác giả: skyvn97

Ngôn ngữ: C++

#include<cstdio>
#include<stack>
#include<vector>
#define MAX   200200
#define FOR(i,a,b) for (int i=(a),_b=(b);i<=_b;i=i+1)
#define REP(i,n) for (int i=0,_n=(n);i<_n;i=i+1)
#define FORE(i,v) for (__typeof((v).begin()) i=(v).begin();i!=(v).end();i++)
using namespace std;
vector<int> g[MAX];
int n,m,cnt,nComp;
int low[MAX],num[MAX],compID[MAX];
bool fre[MAX],isRoot[MAX],isLeaf[MAX];
stack<int> st;
inline void minimize(int &x,const int &y) {
    if (x>y) x=y;
}
void loadgraph(void) {
    scanf("%d%d",&n,&m);
    REP(zz,m) {
        int u,v;
        scanf("%d%d",&u,&v);
        g[u].push_back(v);
    }
    FOR(i,1,n) fre[i]=true;
}
void visit(int u) {
    low[u]=num[u]=++cnt;
    st.push(u);
    FORE(it,g[u]) if (fre[*it]) {
        int v=*it;
        if (num[v]==0) {
            visit(v);
            minimize(low[u],low[v]);
        }
        else minimize(low[u],num[v]);
    }
    if (low[u]==num[u]) {
        nComp++;
        int v;
        do {
            v=st.top();st.pop();
            fre[v]=false;
            compID[v]=nComp;
        }
        while (v!=u);
    }
}
void process(void) {
    FOR(i,1,n) if (num[i]==0) visit(i);
    FOR(i,1,nComp) isRoot[i]=isLeaf[i]=true;
    FOR(u,1,n) FORE(it,g[u]) {
        int v=*it;
        if (compID[u]!=compID[v]) isRoot[compID[v]]=isLeaf[compID[u]]=false;
    }
    FOR(i,1,nComp) if (isRoot[i]) FOR(j,1,nComp) if (isLeaf[j])
        FOR(u,1,n) if (compID[u]==i) FOR(v,1,n) if (compID[v]==j) {
            printf("YES\n%d %d",v,u);
            return;
        }
}
int main(void) {
    loadgraph();
    process();
    return 0;
}

Download