Pagini recente » Cod sursa (job #804796) | Cod sursa (job #1612548) | Cod sursa (job #2055225) | Cod sursa (job #1748530) | Cod sursa (job #2529549)
#include <bits/stdc++.h>
#define DIM 100010
using namespace std;
ifstream fin ("ctc.in");
ofstream fout("ctc.out");
int v[DIM],NIV[DIM],LOW[DIM];
int ctc,n,m,x,y,i,j,g;
stack <int> ST;
vector<int> L[DIM],C[DIM];
void dfs(int nod){
g++;
v[nod]=1;
NIV[nod]=g;
LOW[nod]=g;
ST.push(nod);
for(int i=0;i<L[nod].size();i++){
int vecin = L[nod][i];
if(v[vecin] && NIV[vecin])
LOW[nod]=min(LOW[nod],NIV[vecin]);
else if(!NIV[vecin]){
dfs(vecin);
LOW[nod]=min(LOW[nod],LOW[vecin]);
}
}
if(NIV[nod]==LOW[nod]){
ctc++;
int aux;
do{
aux=ST.top();
C[ctc].push_back(aux);
ST.pop();
v[aux]=0;
}while(aux!=nod);
}
}
int main(){
fin>>n>>m;
for(i=1;i<=m;i++){
fin>>x>>y;
L[x].push_back(y);
}
for(i=1;i<=n;i++)
if(!NIV[i])
dfs(i);
fout<<ctc<<"\n";
for (i=1;i<=ctc;i++) {
for (j=0;j<C[i].size();j++)
fout<<C[i][j]<<" ";
fout<<"\n";
}
return 0;
}