Mai intai trebuie sa te autentifici.
Cod sursa(job #901040)
Utilizator | Data | 28 februarie 2013 23:46:34 | |
---|---|---|---|
Problema | Componente biconexe | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 1.25 kb |
#include<fstream>
#include<vector>
#define nmax 200001
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
int i,j,n,m,niv[nmax],c[nmax],viz[nmax],r1[nmax],r2[nmax],x,y,verge=0,nr=0;
vector<int> G[nmax];
vector<int> sol[nmax];
void add(int a,int b) {
++nr;
int x,y;
do{
x=r1[verge];
y=r2[verge--];
sol[nr].push_back(y);
}while(x!=a || y!=b);
sol[nr].push_back(x);
}
void dfs(int nod,int tata){
niv[nod]=niv[tata]+1;
c[nod]=niv[nod];
viz[nod]=1;
for(int i=0;i<G[nod].size();++i){
int x=G[nod][i];
if(!viz[x]) {
r1[++verge]=nod;
r2[verge]=x;
dfs(x,nod);
if(c[x]<c[nod])
c[nod]=c[x];
if(c[x]>=niv[nod])
add(nod,x);
}
else{
if(x!=tata && c[x]<c[nod])
c[nod]=c[x];
}
}
}
int main () {
f>>n>>m;
for(i=1;i<=m;++i){
f>>x>>y;
G[x].push_back(y);
G[y].push_back(x);
}
dfs(1,0);
g<<nr<<"\n";
for(i=1;i<=nr;++i){
for(j=0;j<sol[i].size();++j){
g<<sol[i][j]<<" ";
}
g<<"\n";
}
return 0;
}