Pagini recente » Cod sursa (job #317349) | Cod sursa (job #3264715) | Cod sursa (job #2512127) | Cod sursa (job #2845471) | Cod sursa (job #781872)
Cod sursa(job #781872)
#include <fstream>
#include <vector>
#define MAXN 100005
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
struct muchie{
int nod1,nod2;};
int n,m,x,y,cnt,nrcbc,dfn[MAXN],low[MAXN],nrfii;
vector<int> G[MAXN],cbc[MAXN];
vector<muchie> stiva;
muchie aux;
void DFS(int p);
int main()
{
int i,j;
f>>n>>m;
for(i=1;i<=m;i++){
f>>x>>y;
G[x].push_back(y);
G[y].push_back(x);}
DFS(1);
g<<nrcbc<<'\n';
for(i=1;i<=nrcbc;i++){
for(j=0;j<cbc[i].size();j++)
g<<cbc[i][j]<<' ';
g<<'\n';}
f.close();
g.close();
return 0;
}
void DFS(int p){
int i;
dfn[p]=(++cnt);
low[p]=cnt;
for(i=0;i<G[p].size();i++){
if(!dfn[G[p][i]]){
aux.nod1=p;
aux.nod2=G[p][i];
stiva.push_back(aux);
DFS(G[p][i]);
if(low[G[p][i]]<low[p])
low[p]=low[G[p][i]];
if(low[G[p][i]]>=dfn[p]){
++nrcbc;
do{
aux=stiva.back();
stiva.pop_back();
cbc[nrcbc].push_back(aux.nod2);}
while(aux.nod1!=p||aux.nod2!=G[p][i]);
cbc[nrcbc].push_back(p);}}
else{
if(dfn[G[p][i]]<low[p])
low[p]=dfn[G[p][i]];}}}