Pagini recente » Cod sursa (job #498247) | Cod sursa (job #2954816) | Cod sursa (job #317538) | Cod sursa (job #53278) | Cod sursa (job #2145639)
#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;
while(q.back() != nod){
v.push_back(q.back());
st[q.back()] = 0;
q.pop_back();
}
v.push_back(q.back());
st[q.back()] = 0;
q.pop_back();
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);
}
dfs(1);
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;
}