Pagini recente » Cod sursa (job #1147657) | Cod sursa (job #2927080) | Cod sursa (job #2977406) | Cod sursa (job #1102758) | Cod sursa (job #2396528)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#define NMAX 100001
using namespace std;
ifstream f1("biconex.in");
ofstream f2("biconex.out");
vector<int> sol[NMAX], v[NMAX];
stack<int> staci;
int n,m,nivel[NMAX],amTrecutPeAici[NMAX], drumIntoarcere[NMAX];
int nrNodDeMijloc;
void dfs(int fiu, int tata){
nivel[fiu] = nivel[tata]+1;
amTrecutPeAici[fiu]=1;
staci.push(fiu);
drumIntoarcere[fiu] = nivel[fiu];
for(auto x : v[fiu]){
if(x == tata) continue;
if(amTrecutPeAici[x]==1){
drumIntoarcere[fiu] = nivel[x]<drumIntoarcere[fiu] ? nivel[x] : drumIntoarcere[fiu];
continue;
}
dfs(x,fiu);
drumIntoarcere[fiu] = drumIntoarcere[x]<drumIntoarcere[fiu] ? drumIntoarcere[x] : drumIntoarcere[fiu];
if(nivel[fiu]<=drumIntoarcere[x]){
++nrNodDeMijloc;
int t;
do{
t = staci.top();
staci.pop();
sol[nrNodDeMijloc].push_back(t);
}while(!staci.empty() && t!=x);
sol[nrNodDeMijloc].push_back(fiu);
}
}
}
int main() {
f1>>n>>m;
int a,b;
for(int i=0;i<m;i++){
f1>>a>>b;
v[a].push_back(b);
v[b].push_back(a);
}
dfs(1,0);
f2<<nrNodDeMijloc<<"\n";
for(int i=1;i<=nrNodDeMijloc;i++){
for(auto x : sol[i]){
f2<<x<<" ";
}
f2<<"\n";
};
return 0;
}