Pagini recente » Cod sursa (job #976678) | Cod sursa (job #161558) | Cod sursa (job #80229) | Cod sursa (job #837191) | Cod sursa (job #2161855)
/// Algoritmul lui Tarjan
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
using VI = vector<int>;
int N, M;
int idx;
vector<VI> G;
VI lvl;
VI L;
vector<bool> inStack;
vector<VI> cc; ///retine componentele tare conexe
VI c; ///retine componenta tare conexa curenta
stack<int> stk;
void ReadGraph();
void Tarjan(int x);
void SCC();
void Write();
int main()
{
ReadGraph();
SCC();
Write();
return 0;
}
void ReadGraph()
{
fin >> N >> M;
G = vector<VI>(N + 1);
L = lvl = VI(N + 1);
inStack = vector<bool>(N + 1);
while(M--)
{
int x, y;
fin >> x >> y;
G[x].push_back(y);
}
}
void Tarjan(int x)
{
lvl[x] = L[x] = ++idx;
stk.push(x); inStack[x] = true;
for(const int& y : G[x])
if(!lvl[y])
{
Tarjan(y);
L[x] = min(L[x], L[y]);
}
else
if (inStack[y])
L[x] = min(L[x], lvl[y]);
if(L[x] == lvl[x])
{
c.clear();
while(!stk.empty())
{
int z = stk.top();
stk.pop();
inStack[z] = false;
c.push_back(z);
if(z == x)
break;
}
cc.push_back(c);
}
}
void SCC()
{
for(int i = 1; i <= N; ++i)
if(lvl[i] == 0)
Tarjan(i);
}
void Write()
{
fout << cc.size() << '\n';
for(auto& c : cc)
{
for(auto& x : c)
fout << x << " ";
fout << '\n';
}
}