Pagini recente » Cod sursa (job #3252359) | Cod sursa (job #2576709) | Cod sursa (job #2265364) | Cod sursa (job #2067596) | Cod sursa (job #875635)
Cod sursa(job #875635)
#include <fstream>
#include <stack>
#include <vector>
#include <algorithm>
#define pb push_back
#define Nmax 100005
using namespace std;
ifstream f("biconex.in"); ofstream g("biconex.out");
int n,m,x,y;
vector <int> adj[Nmax], d(Nmax,-1), low(Nmax);
vector <vector <int> > C;
stack <pair <int, int> > stk;
void CompTC(const int x, const int y)
{ vector <int> con;
int ei,ef;
do
{ ei=stk.top().first, ef=stk.top().second; stk.pop();
con.pb(ei); con.pb(ef);
}
while(ei!=x || ef!=y);
C.pb(con);
}
void DFS(const int n, const int fn, int number)
{ d[n]=low[n]=number;
vector <int> :: iterator it=adj[n].begin(), sf=adj[n].end();
for (; it!=sf ; ++it)
{ if (*it == fn) continue ;
if (d[*it] == -1)
{ stk.push(make_pair(n,*it));
DFS(*it,n,number+1);
low[n]=min(low[n],low[*it]);
if (low[*it]>=d[n]) CompTC(n,*it);
}
else low[n]=min(low[n],d[*it]);
}
}
int main(void)
{ f>>n>>m;
while(m--) {f>>x>>y; adj[x].pb(y); adj[y].pb(x);}
DFS(1,0,0);
g<<C.size()<<"\n";
for(unsigned int i=0; i<C.size(); ++i)
{ sort(C[i].begin(),C[i].end());
C[i].erase(unique(C[i].begin(),C[i].end()),C[i].end());
for (unsigned int j=0; j<C[i].size(); ++j) g<<C[i][j]<<" ";
g<<"\n";
}
g.close(); return 0;
}