Pagini recente » Cod sursa (job #139836) | Cod sursa (job #2579443) | Cod sursa (job #2371296) | Cod sursa (job #2789201) | Cod sursa (job #963272)
Cod sursa(job #963272)
#include<fstream>
#include<vector>
#include<list>
using namespace std;
int n,m;
struct node{
int h, low;
bool v, done;
};
vector<node> N;
vector<list<int> > G;
list<int> stack;
list<list<int> >result;
void visit(int x){
N[x].v = true;
N[x].h = stack.size();
N[x].low = stack.size();
stack.push_back(x);
for(int y: G[x]){
if(N[y].done) continue;
if(!N[y].v)
visit(y);
N[x].low = min(N[x].low, N[y].low);
}
if(N[x].h == N[x].low){
list<int> component;
do{
N[stack.back()].done=true;
component.push_back(stack.back());
stack.pop_back();
}while(component.back() != x);
result.push_back(move(component));
}
}
void read(){
int i=0, x, y;
for(i=0; i<m; i++){
scanf("%d %d",&x, &y);
G[x].push_back(y);
}
}
int main(){
int i;
freopen("ctc.in", "rt", stdin);
freopen("ctc.out", "wt", stdout);
scanf("%d %d",&n,&m);
G.resize(n+1);
N.resize(n+1);
read();
for(i=1; i<=n; i++){
if(N[i].v == false)
visit(i);
}
printf("%d\n", (int)result.size());
while(result.size()){
for(int x: result.front())
printf("%d ", x);
printf("\n");
result.pop_front();
}
fclose(stdin);
fclose(stdout);
return 0;
}