Pagini recente » Cod sursa (job #1125523) | Cod sursa (job #1827072) | Cod sursa (job #1976325) | Cod sursa (job #103081) | Cod sursa (job #1735465)
#include <iostream>
#include <fstream>
#include <stack>
#include <cstdio>
#include <vector>
using namespace std;
vector<int> idx;
vector<int> lowlink;
vector<vector<int> > graph;
vector<vector<int> > ctc;
int nrCtc = 0;
vector<bool> in_stack;
stack<int> s;
int index = 0;
int n,m;
void tarjan (int v)
{
idx[v] = index;
lowlink[v] = index;
index = index+1;
s.push(v);
in_stack[v] = true;
for (int i = 0; i < graph[v].size(); i++)
{
if (idx[graph[v][i]] == -1)
{
tarjan(graph[v][i]);
lowlink[v] = min (lowlink[v], lowlink[graph[v][i]]);
}
else
{
//nu iau in cosiderare arcele transversale
if (in_stack[graph[v][i]] == true)
{
lowlink[v] = min (lowlink[v], lowlink[graph[v][i]]);
}
}
}
if (lowlink[v] == idx[v])
{
nrCtc++;
ctc.resize(ctc.size()+1);
int u = s.top();
s.pop();
//cout<<u<<endl;
in_stack[u] = false;
ctc[nrCtc-1].push_back(u);
while (u!=v && !s.empty())
{
u = s.top();
in_stack[u] = false;
s.pop();
ctc[nrCtc-1].push_back(u);
}
}
}
int main()
{
int x,y;
freopen("ctc.in", "r", stdin);
freopen ("ctc.out", "w", stdout);
scanf("%d %d",&n,&m);
in_stack.resize(n+1, false);
graph.resize(n+1);
lowlink.resize(n+1, -1);
idx.resize(n+1, -1);
for (int i = 1; i<=m; i++)
{
scanf("%d %d",&x,&y);
graph[x].push_back(y);
}
for (int i = 1; i <= n; i++)
{
if (idx[i] == -1)
tarjan (i);
}
cout<<ctc.size()<<endl;
for (int i = 0; i < ctc.size() ;i++)
{
for (int j = 0; j < ctc[i].size();j++)
cout<<ctc[i][j]<<" ";
cout<<endl;
}
return 0;
}