Pagini recente » Cod sursa (job #898197) | Cod sursa (job #1192991) | Cod sursa (job #1843846) | Cod sursa (job #1550123) | Cod sursa (job #2671756)
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
ifstream f ("biconex.in");
ofstream g ("biconex.out");
vector<int> v[100005], dft, low;
vector <vector <int>> c;
stack <pair <int, int> > sk;
int n, m;
void punct_de_articulatie(int x, int y)
{
vector<int> con;
int tx, ty;
//toti copiii lui x din stiva fac parte din componenta conexa
while(tx != x || ty!=y)
{
tx=sk.top().first;
ty=sk.top().second;
sk.pop();
con.push_back(tx);
con.push_back(ty);
}
c.push_back(con);
}
void DFS (int x, int parent, int k)
{
dft[x]=k;
low[x]=k;
for(int i=0; i<v[x].size(); i++) //parcurc toti vecinii lui x
{
//conditia 1: nu o iau pe muchii de intoarcere
//conditia 2: vecinul nu este vizitat
if(v[x][i]!=parent && dft[v[x][i]]==-1)
{
//pun muchia pe care ma duc in stiva
sk.push(make_pair(x, v[x][i]));
DFS(v[x][i], x, k+1); //fac dfs pe vecinul ales
//daca copiii lui x au tutut sa ajunga intr-un nod doar prin o muchie de intparcere
//inseamna ca si x poate, coborand putin si luand acceas muchie
low[x]=min(low[x], low[v[x][i]]);
if(low[v[x][i]]>=dft[x]) //contitia ca x sa fie punct de articulatie
punct_de_articulatie(x, v[x][i]);
}
else
if(dft[v[x][i]]!=-1) //daca nodul e deja vizitat inseamna ca asta e o muchie de intoarcere
{
low[x]=min(low[x], dft[v[x][i]]);//asa ca fac update la low
}
}
}
int main()
{
f>>n>>m;//citest nr de noduri si de muchii
for(int i=0; i<m; i++)//citesc toae muchiile si le pun in lista de adiacenta
{
int x, y;
f>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
dft.resize(n+1); //dft[x] va fi al catelea nod a fost x in parcurgerea dfs
dft.assign(n+1, -1); //deocamdata toatenodurile au valoarea -1, adica nu au fost vizitate
low.resize(n+1); //low[x] va fi dft[p] unde p este cel mai de sus nod la care se poate ajunge
//din x, traversand doar o muchie de intoarcere
DFS(1, 0, 0);
//g<<c.size()<<"\n";
for(int i=0; i< c.size(); i++)
{
sort( c[i].begin(), c[i].end() );
c[i].erase( unique( c[i].begin(), c[i].end() ), c[i].end() );
for(int j=0; j<c[i].size(); j++)
g<<c[i][j]<<" ";
g<<"\n";
}
}