Pagini recente » Cod sursa (job #2362997) | Cod sursa (job #361757) | Cod sursa (job #148828) | Cod sursa (job #1651132) | Cod sursa (job #2117776)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
struct graf{
int nod;
int dist;
graf* next;
};
struct edge{
int v1,v2;
};
vector <int> col(100001);
vector < edge > print;
int Q;
graf* v[100001];
int comp[100001];
int d[100001];
int tati[100001];
int low[100001];
int t = 1;
int c = 1;
int counter=0;
int root =1;
edge st[200001];
int len;
int sonsOfRoot;
void pop(){
edge x;
if(col[st[len].v1]!= Q){
x.v1 = st[len].v1;
x.v2 = Q;
print.push_back(x);
col[st[len].v1] = Q;
}
if(col[st[len].v2]!= Q){
x.v1 = st[len].v2;
x.v2 = Q;
print.push_back(x);
col[st[len].v2] = Q;
}
--len;
}
void add(int a, int b)
{
graf* q = new graf;
q->nod = b;
q->next = v[a];
v[a] = q;
}
void DFS(int node, int dad){
low[node] = d[node] = t;
++t;
++len,
st[len].v1 = dad,
st[len].v2 = node;
comp[node] = c;
graf *p;
p=v[node];
while(p!=NULL){
if(comp[p->nod] == 0){
DFS(p->nod, node),
tati[p->nod] = node;
if(node == root && sonsOfRoot < 2)
++sonsOfRoot;
if(d[node] <= low[p->nod]){
++Q;
++ counter;
while(st[len].v1!=node||st[len].v2!=p->nod){
pop();
}
pop();
}
}
if(p->nod!=dad && low[node] > low[p->nod]){
low[node] = low[p->nod];
}
p = p->next;
}
}
int main()
{
int i,x,y;
int n,m;
fin >> n >> m;
for(i=1;i<=m;++i){
fin >> x >> y;
add(x,y);
add(y,x);
}
for(i=1;i<=n;++i){
if(comp[i]==0){
root = i;
DFS(i,0);
}
}
fout << counter << endl;
for (int i = 0; i < print.size(); i++) {
if(i>=1&&print[i].v2!=print[i-1].v2)
fout << "\n";
fout << print[i].v1 << " ";
}
return 0;
}