Pagini recente » Cod sursa (job #645681) | Cod sursa (job #2154905) | Cod sursa (job #1348922) | Cod sursa (job #928544) | Cod sursa (job #2184215)
#include<bits/stdc++.h>
#define NMAX 100010
using namespace std;
stack<int>S;
int disc[NMAX],low[NMAX],k;
bool inS[NMAX];
vector<int>V[NMAX];
vector<int>CTC[NMAX];
int rs,n,m;
void tarjan(int x) {
S.push(x); inS[x]=1;
disc[x]=low[x]=++k;
for (int i=0; i<V[x].size(); i++) {
int y=V[x][i];
if (!disc[y]) {
tarjan(y);
low[x]=min(low[x],low[y]);
} else if (inS[V[x][i]]) {
low[x]=min(low[x],disc[y]);
}
}
if (disc[x]==low[x]) {
int u; rs++;
do {
u=S.top(); inS[u]=0;
CTC[rs].push_back(u);
S.pop();
} while (u!=x);
}
}
int main() {
ifstream cin("ctc.in");
ofstream cout("ctc.out");
cin>>n>>m;
for (int i=1; i<=m; i++) {
int x,y; cin>>x>>y;
V[x].push_back(y);
}
for (int i=1; i<=n; i++)
if (!disc[i]) tarjan(i);
cout<<rs<<'\n';
for (int i=1; i<=rs; i++) {
for (int j=0; j<CTC[i].size(); j++) {
cout<<CTC[i][j]<<" ";
} cout<<'\n';
}
return 0;
}