Pagini recente » Cod sursa (job #1786224) | Cod sursa (job #1961992) | Cod sursa (job #468065) | Cod sursa (job #1093817) | Cod sursa (job #2805882)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
vector <int> muchii[100001];
bool verif[100001];
bool verif2[100001];
vector <int> cost(100001, 0);
vector <int> low(100001, 0);
vector <int> parent(100001, 5555555);
vector <int> articulatii;
vector <int> noduri;
int n,m,x,y, cont, timp,u=-1;
void AP(int v){
verif[v]=true;
timp++;
low[v]=timp;
cost[v]=timp;
int child=0;
for (int i=0; i<muchii[v].size();i++){
if(!verif[muchii[v][i]]){
child++;
parent[muchii[v][i]]=v;
AP(muchii[v][i]);
low[v]= min(low[v],low[muchii[v][i]]);
if (parent[v]==5555555 && child > 1){
cont++; articulatii.push_back(v);}
if(parent[v]!=5555555 && low[muchii[v][i]] >= cost[v]){
cont++; articulatii.push_back(v);}
}
else if (muchii[v][i] != parent[v])
low[v] = min(low[v], cost[muchii[v][i]]);
}
}
void conex(int nod){
verif2[nod]=true;
if (u==-1){
for (int i=0; i<articulatii.size();i++){
if (nod==articulatii[i])
u=nod;
}
}
cout<<u<<" ";
noduri.push_back(nod);
for (int i=0; i<muchii[nod].size();i++){
int vecin = muchii[nod][i];
for (int j = 0; j<articulatii.size();j++){
if (articulatii[j]==vecin && vecin!= parent[vecin]){
for (int k=0; k<noduri.size();k++){
g<<noduri[k]<<" ";
}
g<<'\n';noduri.clear();u=articulatii[j];
}
}
if(!verif2[vecin])
conex(vecin);
}
}
int main()
{
f>>n>>m;
for (int i=1; i<=m;i++)
{
f>>x>>y;
muchii[x].push_back(y);
muchii[y].push_back(x);
}
AP(1);
g<<cont+1<<'\n';
conex(1);
return 0;
}