Pagini recente » Cod sursa (job #3212241) | Cod sursa (job #1540723) | Cod sursa (job #1440996) | Cod sursa (job #936493) | Cod sursa (job #928739)
Cod sursa(job #928739)
#include <cstdio>
#include <vector>
#include <stack>
#include <algorithm>
#include <utility>
#include <cstdlib>
#define NMAX 100100
using namespace std;
typedef pair <int,int> pereche;
int *Graf[NMAX];
stack < pereche > ST;
vector < vector < int > > Sol;
int dfn[NMAX],low[NMAX];
int n,m,nr;
long degree[NMAX];
inline void citesc(){
int x,y;
freopen("biconex.in","r",stdin);
freopen("biconex.out","w",stdout);
scanf("%d%d",&n,&m);
while(m){
scanf("%d%d",&x,&y);
degree[x]++;
degree[y]++;
--m;
}
for(register int i=1;i<=n;degree[i++]=0)
Graf[i] = (int*)malloc((degree[i]+1)*sizeof(int));
fseek(stdin,0,SEEK_SET);
scanf("%d%d",&n,&m);
for(register int i=1;i<=m;++i){
scanf("%d%d",&x,&y);
Graf[x][++degree[x]] = y;
Graf[y][++degree[y]] = x;
}
}
void scot_muchii(int u,int v){ // scot toate muchiile din stiva pana intalnesc muchia din comp biconexa
vector < int > Temp;
int tu, tv;
do{
tu = ST.top().first;
tv = ST.top().second;
ST.pop();
Temp.push_back(tu);
Temp.push_back(tv);
} while(tu!=u || tv!=v);
Sol.push_back(Temp);
}
void Biconex(int n,int father,int num){
int u;
low[n] = dfn[n] = num;
for(register int i=1;i<=degree[n];++i){
u = Graf[n][i];
if(u!=father)
if(dfn[u] == -1){ // daca nu am vizitat inca nodul
ST.push(pereche(n,u));
Biconex(u,n,num+1);
low[n] = min(low[n],low[u]);
if(low[u] >= dfn[n])
scot_muchii(n,u);
}
else low[n] = min(low[n],dfn[u]);
}
}
int main(){
citesc();
for(register int i=1;i<=n;++i)
dfn[i] = -1;
Biconex(1,0,0);
printf("%d\n",Sol.size());
for(size_t i=0;i<Sol.size();++i){
sort(Sol[i].begin(),Sol[i].end());
Sol[i].erase(unique(Sol[i].begin(),Sol[i].end()),Sol[i].end());
for(size_t j=0;j<Sol[i].size();++j)
printf("%d ",Sol[i][j]);
printf("\n");
}
return 0;
}