Pagini recente » Cod sursa (job #1500589) | Cod sursa (job #2867501) | Cod sursa (job #336219) | Cod sursa (job #450669) | Cod sursa (job #968107)
Cod sursa(job #968107)
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
#define pb push_back
#define mp make_pair
#define x first
#define y second
#define LE 200666
int level[LE],minh[LE],father_edge[LE],nr_sons[LE];
bool viz[LE],viz_edge[LE],vizn[LE],viz_node[LE];;
vector< pair<int,int> > H[LE];
vector<int> bcnx[LE];
int K;
pair<int,int> edge[LE];
void dfs(int nod,int lev) {
int i,N=H[nod].size();
viz_node[nod]=true;
level[nod]=lev;
minh[nod]=lev;
for(i=0; i<N; ++i)
if (viz_node[H[nod][i].x]==false) {
father_edge[H[nod][i].x]=H[nod][i].y;
dfs(H[nod][i].x,lev+1);
minh[nod]=min(minh[nod],minh[H[nod][i].x]);
nr_sons[nod]++;
} else if (level[H[nod][i].x]<level[nod]-1)
minh[nod]=min(minh[nod],level[H[nod][i].x]);
if (minh[nod]>=level[nod]) {
viz_edge[ father_edge[nod] ]=true;
if (nod!=1) {
bcnx[++K].pb(edge[father_edge[nod]].x);
bcnx[K].pb(edge[father_edge[nod]].y);
}
if (nr_sons[nod]>1)
vizn[nod]=true;
}
}
void dfs_2(int ind) {
int nod1=edge[ind].x,nod2=edge[ind].y,i;
viz_edge[ind]=true;
bcnx[K].pb(nod1);
bcnx[K].pb(nod2);
if(vizn[nod1]==false) {
int N=H[nod1].size();
for(i=0; i<N; ++i)
if (viz_edge[H[nod1][i].y]==false)
dfs_2(H[nod1][i].y);
}
nod1=nod2;
if(vizn[nod1]==false) {
int N=H[nod1].size();
for(i=0; i<N; ++i)
if (viz_edge[H[nod1][i].y]==false)
dfs_2(H[nod1][i].y);
}
}
int main() {
int n,m,xx,yy,i;
f>>n>>m;
for(i=1; i<=m; ++i) {
f>>xx>>yy;
H[xx].pb(mp(yy,i));
H[yy].pb(mp(xx,i));
edge[i]=mp(xx,yy);
}
dfs(1,1);
for(i=1; i<=m; ++i)
if (viz_edge[i]==false) {
++K;
dfs_2(i);
}
g<<K<<'\n';
for(i=1; i<=K; ++i)
sort(bcnx[i].begin(),bcnx[i].end());
for(i=1; i<=K; ++i) {
int N=bcnx[i].size();
for(int j=0; j<N; ++j)
if (j==0||bcnx[i][j]!=bcnx[i][j-1])
g<<bcnx[i][j]<<" ";
g<<'\n';
}
f.close();
g.close();
return 0;
}