Pagini recente » Cod sursa (job #364247) | Cod sursa (job #1605261) | Cod sursa (job #1539213) | Cod sursa (job #1297422) | Cod sursa (job #2171185)
#include <iostream>
#include <cstdio>
#include <vector>
#include <stack>
#include <algorithm>
#include <bitset>
#define N 100005
using namespace std;
int n, m, index[N], lowlink[N], global_index, nr;
vector <int> G[N], componente[N];
bitset <N> viz, in_stack;
stack <int> S;
void dfs(int nod)
{
viz[nod] = true;
index[nod] = ++global_index;
lowlink[nod] = index[nod];
S.push(nod);
in_stack[nod] = true;
vector <int>::iterator it;
for(it = G[nod].begin() ; it != G[nod].end() ; ++it)
{
if(!viz[*it])
{
dfs(*it);
lowlink[nod] = min(lowlink[nod] , lowlink[*it]);
}
else
{
if(in_stack[*it])
{
lowlink[nod] = min(lowlink[nod] , lowlink[*it]);
}
}
}
if(lowlink[nod] == index[nod])
{
int x;
do
{
x = S.top();
S.pop();
in_stack[x] = false;
componente[nr].push_back(x);
}while(x != nod);
nr++;
}
}
void afisare()
{
printf("%d\n", nr);
for(int i = 0 ; i < nr ; ++i)
{
for(int j = 0 ; j < componente[i].size() ; ++j)
{
printf("%d ", componente[i][j]);
}
printf("\n");
}
}
void prelucrare()
{
for(int i = 1 ; i <= n ; ++i)
{
if(!viz[i])
{
dfs(i);
}
}
afisare();
}
void citire()
{
scanf("%d %d\n", &n, &m);
int x, y;
for(int i = 0 ; i < m ; ++i)
{
scanf("%d %d\n", &x, &y);
G[x].push_back(y);
}
prelucrare();
}
int main()
{
freopen("ctc.in" , "r" , stdin);
freopen("ctc.out" , "w" , stdout);
citire();
return 0;
}