Pagini recente » Cod sursa (job #1544441) | Cod sursa (job #1247114) | Cod sursa (job #725567) | Cod sursa (job #1947969) | Cod sursa (job #2145648)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define DIM 100002
using namespace std;
ifstream in ("ctc.in");
ofstream out("ctc.out");
int n, m, x, y, viz[DIM], low[DIM], lvl[DIM], niv, st[DIM];
vector<vector<int> > ctc;
vector<int> graf[DIM];
vector <int> q;
void make_ctc(int nod){
vector<int> v;
int x;
do{
x = q.back();
v.push_back(x);
st[x] = 0;
q.pop_back();
}while(x != nod);
ctc.push_back(v);
}
void dfs(int nod){
viz[nod] = 1;
low[nod] = lvl[nod] = ++ niv;
st[nod] = 1;
q.push_back(nod);
for(int i = 0; i < graf[nod].size(); ++ i){
int nodc = graf[nod][i];
if(!viz[nodc])
dfs(nodc);
if(st[nodc])
low[nod] = min(low[nod], low[nodc]);
}
if(low[nod] == lvl[nod])
make_ctc(nod);
}
int main(int argc, const char * argv[]) {
in>>n>>m;
for(int i = 1; i <= m; ++ i){
in>>x>>y;
graf[x].push_back(y);
}
for(int i = 1; i <= n; ++ i)
if(!viz[i])
dfs(i);
out<<ctc.size()<<'\n';
for(int i = 0; i < ctc.size(); ++ i){
for(int j = 0; j < ctc[i].size(); ++ j)
out<<ctc[i][j]<<" ";
out<<'\n';
}
return 0;
}