[6543] 그래프의 싱크

[6543] 그래프의 싱크

#include < bits / stdc + + .h >

using namespace std ;

int n, m, cnt, d[ 100001 ], SN, sn[ 100001 ];

bool checked[ 100001 ];

vector < int > adj[ 100001 ];

vector < vector < int > > scc;

stack < int > s;

int dfs( int cur) {

d[cur] = + + cnt;

s.push(cur);

int res = d[cur];

for ( int next : adj[cur]) {

if (d[next] = = 0 )

res = min(dfs(next), res);

else if ( ! checked[next])

res = min(res, d[next]);

}

if (res = = d[cur]) {

vector < int > temp;

while ( 1 ) {

int x = s.top();

s. pop ();

temp. push_back (x);

checked[x] = true ;

sn[x] = SN;

if (x = = cur) break ;

}

sort(temp. begin (), temp. end ());

scc. push_back (temp);

SN + + ;

}

return res;

}

int main( void ) {

ios_base::sync_with_stdio( 0 );

cin .tie( 0 );

while ( 1 ) {

cin > > n;

if (n = = 0 ) break ;

m = cnt = SN = 0 ;

memset(d, 0 , sizeof (d));

memset(sn, 0 , sizeof (sn));

memset(checked, 0 , sizeof (checked));

int i;

for (i = 0 ; i < = 100000 ; i + + ) adj[i].clear();

scc.clear();

cin > > m;

for (i = 0 ; i < m; i + + ) {

int x, y;

cin > > x > > y;

adj[x - 1 ]. push_back (y - 1 );

}

for (i = 0 ; i < n; i + + )

if (d[i] = = 0 ) dfs(i);

sort(scc. begin (), scc. end ());

int ind[ 100001 ] = { 0 };

for (i = 0 ; i < n; i + + )

for ( int j : adj[i])

if (sn[i] ! = sn[j]) ind[sn[i]] + + ;

for (i = 0 ; i < n; i + + )

if (ind[sn[i]] = = 0 ) cout < < i + 1 < < " " ;

cout < < '

' ;

}

return 0 ;

}

from http://dizlet.tistory.com/262 by ccl(A) rewrite - 2021-12-17 12:26:25