Pagini recente » Cod sursa (job #2720587) | Cod sursa (job #1384908) | Cod sursa (job #2937982) | Cod sursa (job #96358) | Cod sursa (job #2510282)
#include <fstream>
#include <vector>
#include <cstring>
#define N 100000 + 1
#define M 200000 + 1
using namespace std;
ifstream f ( "ctc.in" );
ofstream g ( "ctc.out" );
vector < int > graph[N];
int k, num, low[N], viz[N], st[N], vsol[N], sol[N], lvl;
bool stiva[N];
void dfs ( int node ){
viz[node] = low[node] = lvl;
st[++k] = node;
stiva[node] = 1;
for ( int i = 0; i < graph[node].size(); i++ ){
int new_node = graph[node][i];
if ( viz[new_node] == 0 ){
lvl++;
dfs ( new_node );
low[node] = min ( low[node], low[new_node] );
}
else
if ( stiva[new_node] == 1 )
low[node] = min ( low[node], viz[new_node] );
}
if ( viz[node] == low[node] ){
num++;
sol[num] = sol[num - 1];
while ( st[k] != node ){
stiva[st[k]] = 0;
vsol[ ++ sol[num] ] = st[k];
k--;
}
stiva[st[k]] = 0;
vsol[ ++ sol[num] ] = st[k];
k--;
}
}
int main()
{ int n, m, x, y;
f >> n >> m;
for ( int i = 1; i <= m; i++ ){
f >> x >> y;
graph[x].push_back ( y );
}
lvl = 1;
for ( int i = 1; i <= n; i++ )
if ( viz[i] == 0 )
dfs ( i );
g << num << '\n';
for ( int i = 1; i <= num; i++ ){
for ( int j = sol[i - 1] + 1; j <= sol[i]; j++ )
g << vsol[j] << ' ';
g << '\n';
}
return 0;
}