Pagini recente » Cod sursa (job #99825) | Cod sursa (job #83616) | Cod sursa (job #2180335) | Cod sursa (job #2602462) | Cod sursa (job #2527899)
#include <bits/stdc++.h>
#define DIM 100005
using namespace std;
ifstream fin ("ctc.in");
ofstream fout ("ctc.out");
int n, m, a, b, nrCtc, k;
int low[DIM], niv[DIM];
bitset <DIM> f, prezentStiva;
stack <int> stec;
vector <int> L[DIM], comp[DIM];
void dfs (int nod){
int don, vecin;
k++;
low[nod] = niv[nod] = k;
f[nod] = 1;
prezentStiva[nod] = 1;
stec.push (nod);
for (int i=0; i<L[nod].size(); i++){
vecin = L[nod][i];
if (f[vecin] == 0){
dfs (vecin);
low[nod] = min (low[nod], low[vecin]);
}
else{
if (prezentStiva[vecin]){
low[nod] = min (low[nod], low[vecin]);
}
}
}
if (low[nod] == niv[nod]){
nrCtc++;
do{
don = stec.top();
stec.pop();
prezentStiva[don] = 0;
comp[nrCtc].push_back (don);
}while (don != nod);
}
}
int main(){
fin >> n >> m;
for (;m--;){
fin >> a >> b;
L[a].push_back(b);
}
for (int i=1; i<=n; i++){
if (!f[i]){
dfs (i);
}
}
fout << nrCtc << "\n";
for (int i=1; i<=nrCtc; i++){
for (int j=0; j<comp[i].size(); j++){
fout << comp[i][j] << " ";
}
fout << "\n";
}
return 0;
}