Pagini recente » Cod sursa (job #2840890) | Cod sursa (job #380008) | Istoria paginii runda/corona_day3/clasament | Cod sursa (job #1288776) | Cod sursa (job #2786642)
#include <bits/stdc++.h>
using namespace std;
int n, m, i, x, y, nivel[100005], nivel_min[100005], nr_comp;
stack <int> Steve;
stack <int> Undo;
vector <int> v[100005];
vector <int> bicomp[100005];
bool viz[100005], viz_bicomp[100005];
void Biconex(int x)
{
Steve.push(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];
//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])
{
int aux;
nr_comp ++;
do
{
aux = Steve.top();
bicomp[nr_comp].push_back(aux);
Steve.pop();
}
while(aux != x);
Steve.push(aux);
}
}
else if(nivel[node] < nivel[x] - 1) nivel_min[x] = min(nivel_min[x], nivel_min[node]);
}
}
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
*/