Mai intai trebuie sa te autentifici.
Cod sursa(job #928478)
Utilizator | Data | 26 martie 2013 14:25:15 | |
---|---|---|---|
Problema | Componente tare conexe | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 1.09 kb |
#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(viz[*i]) low[s]=min(low[s],low[*i]);
}
if(low[s]==h[s]) {
int nod;
for(;;) {
nod=st.back(); cc.push_back(nod);
st.pop_back(); viz[nod]=0;
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(!h[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;
}