Pagini recente » Cod sursa (job #1700550) | Cod sursa (job #2293863) | Cod sursa (job #422224) | Cod sursa (job #871540) | Cod sursa (job #3123746)
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 1e5;
// tarjan for SCCs
ifstream fin( "ctc.in" );
ofstream fout( "ctc.out" );
vector <int> edges[NMAX+1];
bool viz[NMAX+1];
stack <int> stiva;
bool inStack[NMAX+1];
int desc[NMAX+1], low[NMAX+1];
int timp;
vector<int> comps[NMAX+1];
int k;
void dfs( int node ) {
viz[node] = true;
desc[node] = low[node] = timp++;
stiva.push( node );
inStack[node] = true;
for( auto vec: edges[node] ) {
if( !viz[vec] ) {
dfs( vec );
low[node] = min( low[node], low[vec] );
}
else if( inStack[vec] )
low[node] = min( low[node], desc[vec] );
}
if( low[node] == desc[node] ) { // head, the reason it works is that we deal with all the lower nodes first
// so everything under node is already processed
while( stiva.top() != node ) {
comps[k].push_back( stiva.top() );
inStack[stiva.top()] = false;
stiva.pop();
}
comps[k].push_back( stiva.top() );
inStack[stiva.top()] = false;
stiva.pop();
k++;
}
}
int main() {
int n, m, i, a, b;
fin >> n >> m;
for( i = 0; i < m; i++ ) {
fin >> a >> b;
edges[a].push_back( b );
}
k = 0;
for( i = 1; i <= n; i++ ) {
if( !viz[i] )
dfs( i );
}
fout << k << "\n";
for( i = 0; i < k; i++ ) {
for( auto x: comps[i] )
fout << x << " ";
fout << "\n";
}
return 0;
}