Pagini recente » Cod sursa (job #1786894) | Cod sursa (job #2543141) | Cod sursa (job #1005607) | Cod sursa (job #218248) | Cod sursa (job #631997)
Cod sursa(job #631997)
#include <stdio.h>
#include <vector>
#include <stack>
using namespace std;
#define MAXN 100005
int n,m;
vector<int> g[MAXN];
vector<int> gt[MAXN];
bool viz[MAXN];
bool vizt[MAXN];
stack<int> st;
vector<int> sol[MAXN];
int cindex = 0;
void dfs(int nod) {
viz[nod] = 1;
for (int i = 0 ; i < g[nod].size() ; ++i) {
if (!viz[g[nod][i]]) {
dfs(g[nod][i]);
}
}
st.push(nod);
}
void dfst(int nod) {
vizt[nod] = 1;
for (int i = 0 ; i < gt[nod].size() ; ++i) {
if (!vizt[gt[nod][i]]) {
dfst(gt[nod][i]);
}
}
sol[cindex].push_back(nod);
}
int main() {
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
scanf("%d %d",&n,&m);
int x,y;
for (int i = 0 ; i < m ; ++i) {
scanf("%d %d",&x,&y);
g[x].push_back(y);
gt[y].push_back(x);
}
for (int i = 1 ; i <= n ; ++i) {
if (!viz[i]) {
dfs(i);
}
}
while (!st.empty()) {
if (!vizt[st.top()]) {
dfst(st.top());
cindex++;
}
st.pop();
}
printf("%d\n",cindex);
for (int i = 0 ; i < cindex ; ++i) {
for (int j = 0 ; j < sol[i].size() ; ++j) {
printf("%d ",sol[i][j]);
}
printf("\n");
}
return 0;
}