Pagini recente » Cod sursa (job #1275590) | Cod sursa (job #1101909) | Cod sursa (job #62825) | Cod sursa (job #770906) | Cod sursa (job #2808412)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
const int NMAX = 1e5;
vector<int> graph[1 + NMAX];
bool visited[1 + NMAX]; bool on_stack[1 + NMAX];
int node_id[1 + NMAX]; int low_link[1 + NMAX];
stack<int> node_stack;
vector<int> scc[1 + NMAX];
int count_scc = 0;
int node_index = 1;
void dfs ( int root ) {
visited[root] = true;
node_id[root] = low_link[root] = node_index ++;
node_stack.push ( root ); on_stack[root] = true;
for ( auto node : graph[root] ) {
if ( !visited[node] ) {
dfs ( node );
if ( on_stack[node] )
low_link[root] = min ( low_link[root], low_link[node] );
}
}
if ( node_id[root] == low_link[root] ) {
count_scc ++;
int curr_node;
do {
curr_node = node_stack.top ();
scc[count_scc].push_back ( curr_node );
on_stack[curr_node] = false;
node_stack.pop ();
}
while ( curr_node != root );
}
}
ifstream fin ( "ctc.in" );
ofstream fout ( "ctc.out" );
int main()
{
int n, m; fin >> n >> m;
for ( int i = 1; i <= m; i ++ ) {
int u, v; fin >> u >> v;
graph[u].push_back ( v );
}
for ( int i = 1; i <= n; i ++ )
if ( !visited[i] )
dfs ( i );
fout << count_scc << "\n";
for ( int i = 1; i <= count_scc; i ++ ) {
for ( auto x : scc[i] )
fout << x << " ";
fout << "\n";
}
return 0;
}