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