Pagini recente » Cod sursa (job #826086) | Cod sursa (job #923803) | Cod sursa (job #1989508) | Cod sursa (job #1067001) | Cod sursa (job #2665275)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <set>
using namespace std;
stack<pair<int, int> > sol;
vector<set<int> > comp;
void punct_critic(int start, int tata, int niv, vector<vector<int> > adiacenta, vector<int> &viz, vector<int> &minim)
{
minim[start] = niv;
viz[start] = niv;
for(int nod: adiacenta[start])
{
if(viz[nod] == 0)
{
sol.push(make_pair(start, nod));
punct_critic(nod, start, niv+1, adiacenta, viz, minim);
minim[start] = min(minim[start], minim[nod]);
if(minim[nod] >= viz[start])
{
set<int> aux;
while(sol.top().first != start || sol.top().second != nod)
{
aux.insert(sol.top().first);
aux.insert(sol.top().second);
sol.pop();
}
aux.insert(sol.top().first);
aux.insert(sol.top().second);
sol.pop();
comp.push_back(aux);
aux.clear();
}
}
else
minim[start] = min(minim[start], viz[nod]);
}
}
int main()
{
ifstream in("biconex.in");
ofstream out("biconex.out");
int n,m;
in>>n>>m;
vector<vector<int> > matrice(n+1, vector<int> (n+1, 0));
vector<vector<int> > adiacenta(n+1);
vector<int> viz(n+1, 0);
vector<int> minim (n+1, 0);
vector<bool> critic (n+1, false);
for(int i=1; i<=m; i++)
{
int x,y,c;
in>>x>>y;
matrice[x][y] = matrice[y][x] = 1;
adiacenta[x].push_back(y);
adiacenta[y].push_back(x);
}
punct_critic(1, 0, 1, adiacenta, viz, minim);
out<<comp.size()<<endl;
for(int i=0; i<comp.size(); i++)
{
for(int nod : comp[i])
out<<nod<<" ";
out<<endl;
}
}