Pagini recente » Cod sursa (job #2729321) | Cod sursa (job #258938) | Cod sursa (job #1289924) | Cod sursa (job #1982960) | Cod sursa (job #2810152)
#include <iostream>
#include <fstream>
#include <stack>
#include <vector>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
const int NMAX=100000;
int N,M,nrc;
vector<int> G[NMAX+1],CTC[NMAX+1];
int D[NMAX+1],Dmin[NMAX+1],Timp=0;
stack<int>S;
bool inSt[NMAX+1];
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) {
D[x]=++Timp;
Dmin[x]=D[x];
S.push(x);
inSt[x]=1;
for(auto &y:G[x]) {
if(D[y]==0) {
DFS(y);
Dmin[x]=min(Dmin[x],Dmin[y]);
} else {
if(inSt[y]==1)///muchie de intoarecere
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]) {
int u;
nrc++;
do {
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;
}