Pagini recente » Cod sursa (job #2147520) | Cod sursa (job #2613034) | Cod sursa (job #2392957) | Cod sursa (job #2957985) | Cod sursa (job #990217)
Cod sursa(job #990217)
#include <stdio.h>
#include <stack>
#include <vector>
#include <map>
#include <algorithm>
#include <set>
using namespace std;
int N, M;
vector<int> adjacence_list[100011];
int index[100011];
int backlink[100011];
int ind = 0;
stack<int> S;
vector<set<int>> result;
int nr = 0;
void read(){
int from, to;
scanf("%d %d", &N, &M);
for(int i = 1; i <= N; ++i){
index[i] = -1;
}
for(int i = 0; i < M; ++i){
scanf("%d %d", &from, &to);
adjacence_list[from].push_back(to);
}
/*
for(int i = 1; i <= N; ++i){
vector<int>::iterator it;
printf("%d ", i);
for(it = adjacence_list[i].begin(); it != adjacence_list[i].end(); ++it){
printf("%d ", *it);
}
}*/
}
void tarjan(int node){
index[node] = ind;
backlink[node] = ind;
++ind;
S.push(node);
//go through neighbours
vector<int>::iterator it;
for(it = adjacence_list[node].begin(); it!= adjacence_list[node].end(); ++it){
if(index[(*it)] == -1){ // if it hasn't been visited yet
tarjan(*it);
backlink[node] = min(backlink[*it], backlink[node]);
}
else if(index[(*it)] != -2){ // if *it is in the stack (-2 means that node has taen part in a scc that was already discovered and discarded)
backlink[node] = min(backlink[node], backlink[*it]);
}
}
//see if node is a root of scc
if(backlink[node] == index[node]){
//printf("intra\n");
++nr;
set<int> s;
result.push_back(s);
int popped;
do{
popped = S.top();
index[popped] = -2;
S.pop();
result.back().insert(popped);
} while(popped != node);
}
}
int main(){
freopen("ctc.in", "r", stdin);
freopen("ctc.out", "w", stdout);
read();
for(int i = 1; i <= N; ++i){
if(index[i] == -1){// not visited
tarjan(i);
}
}
printf("%d\n", nr);
vector<set<int>>::iterator it;
for(it = result.begin(); it != result.end(); ++it){
set<int>::iterator it1;
for(it1 = (*it).begin(); it1 != (*it).end(); ++it1){
printf("%d ", (*it1));
}
printf("\n");
}
return 0;
}