Pagini recente » Cod sursa (job #1376546) | Cod sursa (job #679414) | Statistici Emilian Bold (emilian) | Cod sursa (job #1295137) | Cod sursa (job #928414)
Cod sursa(job #928414)
#include <iostream>
#include <fstream>
#include <vector>
#include <bitset>
#define DN 100005
using namespace std;
typedef vector<int>::iterator it;
int n,m,h[DN],low[DN],sz;
vector<int> gr[DN],st,cc;
bitset<DN> viz;
vector<vector<int> > r;
void dfs(int s) {
st.push_back(s);
viz[s]=1;
h[s]=low[s]=++sz;
for(it i=gr[s].begin(); i!=gr[s].end(); ++i) {
if(!h[*i]) dfs(*i);
low[s]=min(low[s],low[*i]);
}
if(low[s]==h[s]) {
int nod;
for(;;) {
nod=st.back();
viz[nod]=0;
cc.push_back(nod);
st.pop_back();
if(nod==s) break;
}
//cerr<<'\n';
r.push_back(cc);
cc.clear();
}
}
int main()
{
ifstream f("ctc.in");
ofstream g("ctc.out");
f>>n>>m;
for(int i=0; i<m; ++i) {
int a,b;
f>>a>>b;
gr[a].push_back(b);
}
for(int i=1; i<=n; ++i) if(!viz[i]) dfs(i);
g<<r.size()<<'\n';
for(int i=0; i<r.size(); ++i) {
for(int j=0; j<r[i].size(); ++j) g<<r[i][j]<<' ';
g<<'\n';
}
return 0;
}