Pagini recente » Cod sursa (job #1946946) | Cod sursa (job #1795091) | Cod sursa (job #2710466) | Cod sursa (job #793005) | Cod sursa (job #2805898)
#include<iostream>
#include<fstream>
#include<vector>
#include<stack>
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
stack<int>stiva;
int verif[100002],low[100002],cost[100002];
int n,m,cont=0;
vector<int> muchii[100002],componente[100002];
void biconexe(int nod,int parent){
verif[nod]=true;
low[nod]=cost[nod]=cost[parent]+1;
stiva.push(nod);
for (int i=0;i<muchii[nod].size();i++){
if (muchii[nod][i] != parent){
if (verif[muchii[nod][i]])
low[nod]=min(low[nod],cost[muchii[nod][i]]);
else{
biconexe(muchii[nod][i],nod);
low[nod]=min(low[nod],low[muchii[nod][i]]);
if (low[muchii[nod][i]]>=cost[nod]){
cont++;
while (stiva.top()!=muchii[nod][i]){componente[cont].push_back(stiva.top());stiva.pop();}
componente[cont].push_back(muchii[nod][i]);stiva.pop();componente[cont].push_back(nod);
}
}
}
}
}
int main() {
f>>n>>m;
int x,y;
for(int i=1;i<=m;i++){
f>>x>>y;
muchii[x].push_back(y);
muchii[y].push_back(x);
}
for (int i=1;i<=n;i++)
if (verif[i]==0)
biconexe(i,0);
g<<cont<<'\n';
for (int i=1;i<=cont;i++){
for (int j=componente[i].size()-1;j>=0;j--)
g<< componente[i][j]<<" ";
g<<'\n';
}
/* for(int i=1;i<=n;i++){
cout<<low[i];
} */
return 0;
}