Pagini recente » Cod sursa (job #1956993) | Cod sursa (job #1012360) | Cod sursa (job #3245366) | Cod sursa (job #372823) | Cod sursa (job #1459437)
#include <stdio.h>
#include <vector>
#define MAX 100005
#define min(a, b) (a < b ? a : b)
using namespace std;
vector<int> l[MAX], s, con;
vector< vector<int> > C;
int n, m, i, j, x, y, index[MAX], lowlink[MAX], ind;
bool onStack[MAX];
void strongconnect(int v);
int main(){
freopen("ctc.in", "r", stdin);
freopen("ctc.out", "w", stdout);
scanf("%d%d", &n, &m);
for(i = 0; i < m; i++){
scanf("%d%d", &x, &y);
l[x].push_back(y);
}
for(i = 1; i <= n; i++)
index[i] = -1;
for(i = 1; i <= n; i++)
if(index[i] == -1)
strongconnect(i);
printf("%d\n", C.size());
for(i = 0; i < C.size(); i++){
for(j = 0; j < C[i].size(); j++)
printf("%d ", C[i][j]);
printf("\n");
}
return 0;
}
void strongconnect(int v){
s.push_back(v);
lowlink[v] = index[v] = ind;
ind++;
onStack[v] = true;
vector<int>::iterator it;
for(it = l[v].begin(); it < l[v].end(); it++)
if(index[*it] == -1){
strongconnect(*it);
lowlink[v] = min(lowlink[v], lowlink[*it]);
}
else if(onStack[*it])
lowlink[v] = min(lowlink[v], index[*it]);
if(lowlink[v] == index[v]){
int w = 0;
con.clear();
do{
w = s.back();
con.push_back(w);
onStack[w] = false;
s.pop_back();
}while(w != v);
C.push_back(con);
}
}