Pagini recente » Cod sursa (job #647755) | Cod sursa (job #2727736) | Cod sursa (job #1828358) | Cod sursa (job #2895416) | Cod sursa (job #2118747)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
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;
vector <edge> cache[100001];
int Q;
graf* v[100001];
bool vis[100001];
int d[100001];
int low[100001];
int c = 1;
int t;
stack <edge> stk;
int len;
void load(){
edge y,x;
y = stk.top();
if(col[y.v1]!= Q){
x.v1 = y.v1;
x.v2 = Q;
print.push_back(x);
col[y.v1] = Q;
}
if(col[y.v2]!= Q){
x.v1 = y.v2;
x.v2 = Q;
print.push_back(x);
col[y.v2] = Q;
}
stk.pop();
}
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;
edge x;
x.v1 = dad;
x.v2 = node;
if(dad)
stk.push(x);
vis[node] = 1;
graf *p = v[node];
while(p!=NULL){
if(vis[p->nod] == 0){
DFS(p->nod, node);
if(d[node] <= low[p->nod]){
++Q;
while(stk.top().v1!=node||stk.top().v2!=p->nod){
load();
}
load();
}
if(low[node] > low[p->nod]){
low[node] = low[p->nod];
}
}
if(p->nod!=dad && low[node] > d[p->nod]){
low[node] = d[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(vis[i]==0)
DFS(i,0);
fout << Q << 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;
}