Pagini recente » Cod sursa (job #1960628) | Cod sursa (job #950487) | Cod sursa (job #1642471) | Cod sursa (job #382508) | Cod sursa (job #1730930)
#include <bits/stdc++.h>
#define Vmax 100002
#define pb(x) push_back(x)
#define Emax 2 * Nmax
#define NIL -1
FILE *fin = freopen("ctc.in", "r", stdin);
FILE *fout = freopen("ctc.out", "w", stdout);
using namespace std;
int V, E, st[Vmax], disc[Vmax], low[Vmax], nscc;
vector <int> G[Vmax];
vector <int> sol[Vmax];
bitset <Vmax> onSt;
void read()
{
int u, v;
scanf("%d %d", &V, &E);
while(E --)
{
scanf("%d %d", &u, &v);
G[u].pb(v);
}
}
int Min(int x, int y)
{
return x < y ? x : y;
}
void DFS(int u, int depth)
{
int v;
disc[u] = low[u] = depth;
st[++ st[0]] = u;
onSt.set(u);
int sz = G[u].size();
for(int i = 0; i < sz; ++ i)
{
v = G[u][i];
if(disc[v] == NIL)
{
DFS(v, depth + 1);
low[u] = Min(low[u], low[v]);
} /// forward (tree) edge
else if(onSt.test(v) == 1)
low[u] = Min(low[u], low[v]); /// back edge
/// else we encounter a cross edge which should be avoid
}
if(low[u] == disc[u]) /// root of subtree
{
++ nscc;
do
{
v = st[st[0] --];
onSt.reset(v);
sol[nscc].pb(v);
}while(v != u);
}
}
void solve()
{
int i;
for(i = 1; i <= V; ++ i)
{
disc[i] = NIL;
}
for(i = 1; i <= V; ++ i)
{
if(disc[i] == NIL)
DFS(i, 0);
}
}
void write()
{
printf("%d\n", nscc);
for(int i = 1; i <= nscc; ++ i)
{
int sz = sol[i].size();
for(int j = 0; j < sz; ++ j)
printf("%d ", sol[i][j]);
printf("%\n");
}
}
int main()
{
read();
solve();
write();
return 0;
}