Pagini recente » Cod sursa (job #1243672) | Cod sursa (job #1023838) | Cod sursa (job #1875596) | Cod sursa (job #2284759) | Cod sursa (job #3199445)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
const int NMAX=100000;
int N,M,nrc;///nrc=nr comp tari conexe
vector <int> G[NMAX+1],CTC[NMAX+1];
int D[NMAX+1],Dmin[NMAX+1],Timp=0;
stack <int> S;
bool inSt[NMAX+1];///inSt[i] <==> i este in stiva
ifstream f("ctc.in");
ofstream g("ctc.out");
void citire()
{
int x,y;
f>>N>>M;
for(int i=1;i<=M;i++)
{
f>>x>>y;
G[x].push_back(y);
}
}
void DFS(int x)///Tarjan
{
D[x]=++Timp;
Dmin[x]=D[x];
S.push(x);
inSt[x]=1;
for(auto &y:G[x])
{
if(D[y]==0)///Muchie de arbore
{
DFS(y);
Dmin[x]=min(Dmin[x],Dmin[y]);
}
else
{
if(inSt[y]==1)///Muchie de intoarcere
Dmin[x]=min(Dmin[x],D[y]);
///Altfel este o muchie inainte sau muchie cross catre alta componenta conexa
}
}
///Daca x nu poate urca mai sus de x, atunci el este radacina unei CTC
if(Dmin[x]==D[x])///x este radacina unei CTC
{
int u;
nrc++;
do ///Scoatem nodurile CTC de pe stiva
{
u=S.top();
CTC[nrc].push_back(u);
S.pop();
inSt[u]=0;
}
while(x!=u);
}
}
void afisare()
{
g<<nrc<<'\n';
for(int i=1;i<=nrc;i++)
{
for(auto &x: CTC[i])
g<<x<<' ';
g<<'\n';
}
}
int main()
{
citire();
for(int i=1;i<=N;i++)
{
if(D[i]==0)
DFS(i);
}
afisare();
f.close();
g.close();
return 0;
}