Pagini recente » Cod sursa (job #2695174) | Cod sursa (job #3258651) | Cod sursa (job #1075555) | Cod sursa (job #3208350) | Cod sursa (job #3280242)
///tarjan tuti tarzanu mati...
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
vector<int> G[105] , componente[105];
stack <int> s;
int n , m;
int low[105] , num[105];
bool v[105] , on_stack[105];
int index , nrc;
void citire()
{
int x , y;
cin >> n >> m ;
for(int i = 1 ; i<=m ; ++i)
{
cin >> x>>y;
G[x].push_back(y);
}
}
void dfs(int nod)
{
v[nod] = 1; on_stack[nod] = 1;
index++;
num[nod] = low[nod] = index;
s.push(nod);
for(auto e : G[nod])
if(!v[e])
{
dfs(e);
low[nod] = min(low[nod] , low[e]);
}
else if(on_stack[e]) low[nod] = min(low[nod] , low[e]);
if(num[nod] == low[nod])
{
nrc++;
while(s.top() != nod)
{
componente[nrc].push_back(s.top());
on_stack[s.top()] = 0 ;
s.pop();
}
s.pop();
on_stack[nod] = 0 ;
componente[nrc].push_back(nod);
}
}
int main()
{
citire();
for(int i = 1 ; i<= n ; ++i)
if(!v[i])
dfs(i);
cout << nrc << '\n';
for(int i = 1 ; i<=nrc ; ++i)
{
for(auto e : componente[i])
cout << e << ' ';
cout << '\n';
}
}