Pagini recente » Cod sursa (job #1283576) | Cod sursa (job #872134) | Cod sursa (job #2625941) | Cod sursa (job #2456737) | Cod sursa (job #2972306)
#include <bits/stdc++.h>
#define MAX 100002
using namespace std;
int n,m,x,y,st[MAX],low[MAX],id[MAX],inst[MAX],cnt,vf,nrcomp;
vector<int> v[MAX],comp[MAX];
ifstream fin("ctc.in");
ofstream fout("ctc.out");
void dfs(int nod){
st[++vf] = nod;
inst[nod] = 1;
id[nod] = low[nod] = ++cnt;
for(int vecin: v[nod]){
if(id[vecin] == -1){
dfs(vecin);
}
if(inst[vecin]){
low[nod] = min(low[nod], low[vecin]);
}
}
if(id[nod] == low[nod]){
nrcomp++;
while(1){
comp[nrcomp].push_back(st[vf]);
inst[st[vf]] = 0;
low[st[vf]] = id[nod];
vf--;
if(st[vf+1] == nod){
break;
}
}
}
}
int main()
{
fin >> n >> m;
for(int i = 1; i <= m; i++){
fin >> x >> y;
v[x].push_back(y);
}
memset(id, -1, sizeof(id));
for(int i = 1; i <= n; i++){
if(id[i] == -1){
vf = 0;
dfs(i);
}
}
fout << nrcomp << "\n";
for(int i = 1; i <= nrcomp; i++){
for(int it: comp[i]){
fout << it << " ";
}
fout << "\n";
}
return 0;
}