Pagini recente » Monitorul de evaluare | Cod sursa (job #1332449) | Cod sursa (job #1723652) | Cod sursa (job #679919) | Cod sursa (job #2155137)
#include <iostream>
#include <cstdio>
#include <vector>
#include <stack>
#include <bitset>
#include <algorithm>
#define N 100005
using namespace std;
int n, m, lowlink[N], index[N], nr, global_index = 1;
vector <int> G[N];
vector <int> componente[N];
stack <int> S;
bitset <N> viz;
bitset <N> in_stack;
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 dfs(int nod)
{
index[nod] = global_index;
lowlink[nod] = index[nod];
global_index++;
viz[nod] = true;
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();
in_stack[x] = false;
S.pop();
componente[nr].push_back(x);
}while(x != nod);
nr++;
}
}
void solve()
{
for(int i = 1 ; i <= n ; ++i)
{
if(!viz[i])
{
dfs(i);
}
}
}
void citire()
{
scanf("%d %d\n", &n, &m);
int a, b;
for(int i = 0 ; i < m ; ++i)
{
scanf("%d %d\n", &a, &b);
G[a].push_back(b);
}
solve();
afisare();
}
int main()
{
freopen("ctc.in", "r", stdin);
freopen("ctc.out", "w", stdout);
citire();
return 0;
}