Pagini recente » Cod sursa (job #392049) | Cod sursa (job #1525200) | Cod sursa (job #864748) | Cod sursa (job #3221367) | Cod sursa (job #2786612)
#include <bits/stdc++.h>
using namespace std;
int n, m, i, x, y, nivel[100005], nivel_min[100005], nr_comp;
struct muchie
{
int head1;
int head2;
};
stack <muchie> Steve;
stack <int> Undo;
vector <int> v[100005];
vector <int> bicomp[100005];
bool viz[100005], viz_bicomp[100005];
void Biconex(int x)
{
viz[x] = true;
for(int i = 0; i < v[x].size(); i ++)
{
int node = v[x][i];
if(viz[node] == false)
{
//Setam nivelul nodului nou gasit
nivel[node] = nivel[x] + 1;
nivel_min[node] = nivel[node];
//Adaugam o muchie noua in stiva de muchii
muchie aux;
aux.head1 = x;
aux.head2 = node;
Steve.push(aux);
//DFS
Biconex(node);
//Actualizare nivel minim
nivel_min[x] = min(nivel_min[x], nivel_min[node]);
//Verificare punct critic
if(nivel[x] <= nivel_min[node])
{
nr_comp ++;
muchie aux1 = Steve.top();
while(!Steve.empty())
{
if(viz_bicomp[aux1.head1] == false)bicomp[nr_comp].push_back(aux1.head1), viz_bicomp[aux1.head1] = true, Undo.push(aux1.head1);
if(viz_bicomp[aux1.head2] == false)bicomp[nr_comp].push_back(aux1.head2), viz_bicomp[aux1.head2] = true, Undo.push(aux1.head2);
Steve.pop();
if((aux1.head1 == x && aux1.head2 == node)|| (aux1.head1 == node && aux1.head2 == x))break;
aux1 = Steve.top();
}
while(!Undo.empty())
{
viz_bicomp[Undo.top()] = false;
Undo.pop();
}
}
}
else if(nivel[node] < nivel[x] - 1)
{
nivel_min[x] = min(nivel_min[x], nivel_min[node]);
muchie aux;
aux.head1 = node;
aux.head2 = x;
Steve.push(aux);
}
}
}
int main()
{
ifstream f("biconex.in");
ofstream g("biconex.out");
f >> n >> m;
for(i = 1; i <= m; i ++)
{
f >> x >> y;
v[x].push_back(y);
v[y].push_back(x);
}
for(i = 1; i <= n; i ++)
if(viz[i] == false)
{
nivel[i] = 1;
nivel_min[i] = 1;
Biconex(i);
}
g << nr_comp << "\n";
for(i = 1; i <= nr_comp; i ++)
{
for(int j = 0; j < bicomp[i].size(); j ++)
g << bicomp[i][j] << " ";
g << "\n";
}
return 0;
}
/*
8 10
1 2
1 7
2 6
2 7
3 4
3 5
3 6
4 5
5 6
7 8
*/