Pagini recente » Cod sursa (job #2204188) | Cod sursa (job #1421620) | Cod sursa (job #2114286) | Cod sursa (job #2664039) | Cod sursa (job #2899948)
#include <bits/stdc++.h>
using namespace std;
const int DIM = 100005;
ifstream in("biconex.in");
ofstream out("biconex.out");
struct node
{
int key;
node *next;
}*L[DIM];
int N, M;
int low[DIM], niv[DIM];
stack <pair <int, int> > stk;
node *C[DIM];
int nr_comp;
void add(int x, int y, node *l[])
{
node *p = new node;
p->key = y;
p->next = l[x];
l[x] = p;
}
void read(int &N, int &M)
{
in>>N>>M;
int x, y;
for(int i=1; i<=M; i++)
{
in>>x>>y;
add(x,y,L);
add(y,x,L);
}
}
void c_bic(int x, int y, int indice)
{
int tx, ty;
do
{
tx = stk.top().first, ty = stk.top().second;
stk.pop();
add(indice, ty, C);
}
while(tx != x && ty != y);
add(indice, x, C);
}
void DFS(int x, int fx, int level)
{
niv[x] = low[x] = level;
for(node *p = L[x]; p != nullptr; p = p->next)
{
if(p->key == fx)
continue;
if(niv[p->key] == 0)
{
stk.push(make_pair(x, p->key));
DFS(p->key, x, level+1);
low[x] = min(low[x], low[p->key]);
if(niv[x] <= low[p->key])
{
c_bic(x,p->key, nr_comp);
nr_comp++;
}
}
else
low[x] = min(low[x], niv[p->key]);
}
}
void afisare(int lung, node *l[])
{
for(int i=0; i<lung; ++i)
{
for(node *p = l[i]; p != nullptr; p = p->next)
out<<p->key<<" ";
out<<"\n";
}
}
int main()
{
read(N,M);
low[1] = niv[1] = 0;
DFS(1, 0, 0);
out<<nr_comp<<"\n";
afisare(nr_comp, C);
}