Pagini recente » Cod sursa (job #2006824) | Rating Dudau Claudia Maria (Claudia7) | Cod sursa (job #1528514) | Cod sursa (job #433071) | Cod sursa (job #1244943)
#include <iostream>
#include <stack>
#include <vector>
#define MAX 100001
using namespace std;
int N, M;
stack<int> st;
vector<vector<int>> adj(MAX);
vector<vector<int>> adjRev(MAX);
vector<bool> marked(MAX, false);
vector<vector<int>> answer;
vector<int> ans;
void dfs(int source){
for(int i = 0; i < adj[source].size(); i++){
if(!marked[adj[source][i]]){
marked[adj[source][i]] = true;
dfs(adj[source][i]);
}
}
st.push(source);
}
void dfsRev(int source){
for(int i = 0; i < adjRev[source].size(); i++){
if(!marked[adjRev[source][i]]){
marked[adjRev[source][i]] = true;
dfsRev(adjRev[source][i]);
}
}
ans.push_back(source);
}
int main(){
int from, to;
freopen("ctc.in", "r", stdin);
freopen("ctc.out", "w", stdout);
scanf("%d%d", &N, &M);
for(int i = 0; i < M; i++){
scanf("%d%d", &from, &to);
adj[--from].push_back(--to);
adjRev[to].push_back(from);
}
for(int i = 0; i < N; i++){
if(!marked[i])
dfs(i);
}
marked.assign(MAX, false);
while(!st.empty()){
if(!marked[from = st.top()]){
ans.clear();
marked[from] = true;
dfsRev(from);
answer.push_back(ans);
}
st.pop();
}
printf("%d\n", answer.size());
for(int i = 0; i < answer.size(); i++){
for(int j = 0; j < answer[i].size(); j++){
printf("%d ", answer[i][j]+1);
}
printf("\n");
}
return 0;
}