Pagini recente » Cod sursa (job #1530256) | Cod sursa (job #3253012) | Cod sursa (job #886586) | Cod sursa (job #1561713) | Cod sursa (job #2648620)
#include <bits/stdc++.h>
#define DIM 100005
using namespace std;
ifstream f("biconex.in");
ofstream g("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){
f>>N>>M;
int x, y;
for(int i=1; i<=M; i++){
f>>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){
//x = nod curent, fx = father(x);
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]); //unde x - p->key este muchie de intoarcere in dfs
}
}
void afisare(int lung, node *l[]){
for(int i=0; i<lung; ++i){
for(node *p = l[i]; p != nullptr; p = p->next)
g<<p->key<<" ";
g<<"\n";
}
}
int main()
{
read(N,M);
low[1] = niv[1] = 0;
DFS(1, 0, 0);
g<<nr_comp<<"\n";
afisare(nr_comp, C);
}