Pagini recente » Cod sursa (job #29488) | Cod sursa (job #57445) | Cod sursa (job #3031724) | Autentificare | Cod sursa (job #2525926)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>
#define NMAX 10005
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
vector <int> G[NMAX], ans[NMAX];
vector <int> dfsDiscover, dfsLow, articulationVertex, dfsParent, visited;
stack <int> st;
int timex, dfsRoot, rootChildren, N, M, K;
void articulationPoint(int node)
{
int nodex;
++timex;
st.push(node);
dfsDiscover[node] = dfsLow[node] = timex;
for(int j = 0; j < G[node].size(); j++){
nodex = G[node][j];
if(!dfsDiscover[nodex]){
dfsParent[nodex] = node;
if(node == dfsRoot){
rootChildren++;
}
articulationPoint(nodex);
dfsLow[nodex] = min(dfsLow[node],dfsLow[nodex]);
if(dfsLow[nodex] >= dfsDiscover[node]){
articulationVertex[node] = true;
++K;
while(st.top() != nodex){
ans[K].push_back(st.top());
st.pop();
}
ans[K].push_back(node);
ans[K].push_back(nodex);
st.pop();
}
}
else{
if(nodex != dfsParent[node]){
dfsLow[node] = min(dfsLow[node],dfsDiscover[nodex]);
}
}
}
}
int main()
{
int x, y;
fin >> N >> M;
for(int i = 1; i <= M; i++){
fin >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
dfsParent.assign(N + 1,-1);
articulationVertex.assign(N + 1,0);
dfsLow.assign(N + 1,0);
dfsDiscover.assign(N + 1,0);
for(int i = 1; i <= N; i++){
if(!dfsDiscover[i]){
dfsRoot = i;
rootChildren = 0;
articulationPoint(i);
articulationVertex[dfsRoot] = (rootChildren > 1);
}
}
fout << K << "\n";
for(int i = 1; i <= K; i++){
for(int j = 0; j < ans[i].size(); j++){
fout << ans[i][j] << " ";
}
fout << "\n";
}
return 0;
}