Pagini recente » Cod sursa (job #2046959) | Cod sursa (job #2779533) | Cod sursa (job #1585595) | Cod sursa (job #1869444) | Cod sursa (job #2077747)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream in ("ctc.in");
ofstream out ("ctc.out");
#define MIN(a ,b) ((a < b) ? a : b)
int const nmax = 100000;
vector<int> g[5 + nmax];
vector<int> sol[5 + nmax];
vector<int> comp;
int solp = 0;
int idx[5 + nmax] ,lowlink[5 + nmax];
int in_stack[5 + nmax];
int indecs = 0;
void dfs(int node){
idx[node] = lowlink[node] = indecs;
indecs++;
in_stack[node] = 1;
comp.push_back(node);
for(int i = 0 ; i < g[node].size() ;i++){
int newnode = g[node][i];
if(idx[newnode] == -1){
dfs(newnode);
lowlink[node] = MIN(lowlink[node] ,lowlink[newnode]);
///daca e mai mare nu ne intereseaza
///dar daca e mai mic =>
///var 1 = e de la alta componenta conexa
///var 2 = e din componenta noastra
///dar nu poate fi din alta componenta conexa deoarece nodurile care sunt considerate
///vor fi ori din stack(adica componenta noastra) ori nevizitate
///e din componenta noastra
} else if(in_stack[newnode] == 1){///e din componenta noastra conexa
lowlink[node] = MIN(lowlink[node] ,lowlink[newnode]);
}
}
if(idx[node] == lowlink[node]){///e node radacina?
int newnode;
do{
newnode = comp.back();
sol[solp].push_back(newnode);
in_stack[newnode] = 0;
comp.pop_back();
} while(0 < comp.size() && newnode != node);
solp++;
}
}
int main()
{
int n , m;
in>>n>>m;
for(int i = 1 ; i <= m ;i++){
int x , y;
in>>x>>y;
g[x].push_back(y);
}
for(int i = 1 ; i <= n ;i++)
idx[i] = -1;
for(int i = 1 ; i <= n ;i++){
if(idx[i] == -1){
dfs(i);
}
}
out<<solp<<'\n';
for(int i = 0 ; i < solp ;i++){
for(int j = 0 ; j < sol[i].size() ;j++){
out<<sol[i][j]<<" ";
}
out<<'\n';
}
return 0;
}