Pagini recente » Cod sursa (job #794668) | Cod sursa (job #2136765) | Cod sursa (job #3037678) | Cod sursa (job #3249145) | Cod sursa (job #1468673)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
const int Nmax = 100001;
int N,M;
vector<int> Adj[Nmax];
int lowlink[Nmax];
int link[Nmax];
bool seen[Nmax];
int idx = 0;
stack<int> S;
vector< vector<int> > Comp;
void Tarjan(int node)
{
lowlink[node] = ++idx;
link[node] = idx;
seen[node] = 1;
S.push(node);
for(vector<int>::iterator it = Adj[node].begin(); it != Adj[node].end(); ++it)
{
if(seen[*it])
lowlink[node] = min(lowlink[node],lowlink[*it]);
else
{
Tarjan(*it);
lowlink[node] = min(lowlink[node],lowlink[*it]);
}
}
if(link[node] == lowlink[node])
{
Comp.push_back(vector<int>());
while(S.top() != node)
{
Comp.back().push_back(S.top());
S.pop();
}
Comp.back().push_back(S.top());
S.pop();
}
}
int main()
{
ifstream fin("ctc.in");
ofstream fout("ctc.out");
fin >> N >> M;
for(int i = 1; i <= M; i++)
{
int a,b;
fin >> a >> b;
Adj[a].push_back(b);
}
for(int i = 1; i <= N; i++)
if(!seen[i])
Tarjan(i);
fout << Comp.size() << "\n";
for(int i = 0; i < Comp.size(); i++)
{
for(int j = 0; j < Comp[i].size(); j++)
fout << Comp[i][j] << " ";
fout << "\n";
}
}