Pagini recente » Cod sursa (job #1182213) | Cod sursa (job #4446) | Cod sursa (job #2283544) | Cod sursa (job #1320596) | Cod sursa (job #1074576)
#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>
#define minim(a,b) (a<b?a:b)
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
int n,m,niv,CB;
int low[100011];
bool viz[100011];
vector<int> L[100011],c[100011];
stack<pair<int,int> > S;
void dfs(int nod,int niv,int tata){
int x,y;
pair<int,int> p;
low[nod]=niv;
viz[nod]=true;
for(register int i=0;i<L[nod].size();i++){
if(L[nod][i]==tata)
continue;
if(!viz[L[nod][i]]){
//pun in stiva muchua nod,L[nod][i]
S.push(make_pair(nod,L[nod][i]));
dfs(L[nod][i],niv+1,nod);
if (low[ L[nod][i] ] >= niv) {
// plecarea pe muchia nod,L[nod][i] a produs o CB
// scot toate muchiile din stiva pana la aceasta inclusiv
// si toate muchiile sintre nodurile ce apar la muchii din
// stiva sunt o CB
CB++;
x=nod,y=L[nod][i];
do{
p=S.top();
c[CB].push_back(p.second);
c[CB].push_back(p.first);
S.pop();
}while(x!=p.first || y!=p.second);
}
}
low[nod]=minim(low[nod],low[L[nod][i]]);
}
}
int main(void){
register int i,j,x,y;
f>>n>>m;
for(i=1;i<=m;i++){
f>>x>>y;
L[x].push_back(y);
L[y].push_back(x);
}
dfs(1,1,0);
g<<CB<<"\n";
for(i=1;i<=CB;i++){
sort(c[i].begin(),c[i].end());
g<<c[i][0]<<" ";
for(j=1;j<c[i].size();j++)
if(c[i][j]!=c[i][j-1]) g<<c[i][j]<<" ";
g<<"\n";
}
f.close();
g.close();
return 0;
}