Pagini recente » Cod sursa (job #1378892) | Cod sursa (job #894497) | Cod sursa (job #1545811) | Cod sursa (job #1289414) | Cod sursa (job #2143017)
#include<bits/stdc++.h>
#define NMAX 100010
using namespace std;
vector<int>V[NMAX];
bool inStack[NMAX];
int disc[NMAX], low[NMAX];
stack<int>S;
int n,m,nr;
vector<int>::iterator it;
vector<int>CTC[NMAX];
int rs;
int u;
void tarjan(int x) {
disc[x]=++nr;
low[x]=nr;
S.push(x);
inStack[x]=1;
for (int i=0; i<V[x].size(); i++) {
int y=V[x][i];
if (disc[y]==0) {
tarjan(y);
low[x] = min(low[x], low[y]);
} else if (inStack[y]) {
low[x] = min(low[x], disc[y]);
}
}
if (disc[x]==low[x]) {
rs++;
do {
u=S.top();
S.pop();
CTC[rs].push_back(u);
inStack[u]=0;
} 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 (it=CTC[i].begin(); it!=CTC[i].end(); ++it) cout<<*it<<" ";
cout<<'\n';
}
return 0;
}
//DEBUG dc nu merge
/*for (it=V[x].begin(); it!=V[x].end(); it++) {
int y=*it; cout<<'.'<<y<<'.';
if (disc[y]==0) { cout<<"e";
tarjan(y);
// low[x] = min(low[x], low[y]);
} /*else if (inStack[y]) {
low[x] = min(low[x], disc[y]);
}*/
// }*/