Pagini recente » Cod sursa (job #1387317) | Cod sursa (job #863533) | Istoria paginii runda/simulare_de_oni_9/clasament | Cod sursa (job #582146) | Cod sursa (job #2665264)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <set>
using namespace std;
int niv_punct = 0;
stack<pair<int, int> > sol;
vector<set<int> > comp;
void punct_critic(int start, vector<vector<int> > adiacenta, vector<bool> &critic, vector<bool> &viz, vector<int> &niv, vector<int> &minim, vector<int> &tata)
{
int child = 0;
viz[start] = true;
niv[start] = minim[start] = niv_punct++;
for(int nod : adiacenta[start])
{
if(!viz[nod])
{
child++;
tata[nod] = start;
sol.push(make_pair(start, nod));
punct_critic(nod, adiacenta, critic, viz, niv, minim, tata);
minim[start] = min(minim[start], minim[nod]);
if(tata[start] == -1 && child > 1)
{
critic[start] = true;
set<int> aux;
while(sol.top().first != start || sol.top().second != nod)
{
//cout<<sol.top().first<<" "<<sol.top().second<<"---";
aux.insert(sol.top().first);
aux.insert(sol.top().second);
sol.pop();
}
//cout<<sol.top().first<<" "<<sol.top().second<<endl;
aux.insert(sol.top().first);
aux.insert(sol.top().second);
sol.pop();
comp.push_back(aux);
aux.clear();
}
if(tata[start] != -1 && minim[nod] >= niv[start])
{
critic[start] = true;
set<int> aux;
while(sol.top().first != start || sol.top().second != nod)
{
//cout<<sol.top().first<<" "<<sol.top().second<<"---";
aux.insert(sol.top().first);
aux.insert(sol.top().second);
sol.pop();
}
//cout<<sol.top().first<<" "<<sol.top().second<<endl;
aux.insert(sol.top().first);
aux.insert(sol.top().second);
sol.pop();
comp.push_back(aux);
aux.clear();
}
}
else if(nod != tata[start])
{
minim[start] = min(minim[start], niv[nod]);
if(niv[nod] < niv[start])
sol.push(make_pair(start, 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<bool> viz(n+1, false);
vector<int> tata (n+1, -1);
vector<int> niv (n+1, 0);
vector<int> minim (n+1, 0);
vector<bool> critic (n+1, false);
vector<int> status (n+1,0);
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, adiacenta, critic, viz, niv, minim, tata);
set<int> aux;
while(!sol.empty())
{
aux.insert(sol.top().first);
aux.insert(sol.top().second);
sol.pop();
}
comp.push_back(aux);
out<<comp.size()<<endl;
for(int i=0; i<comp.size(); i++)
{
for(int nod : comp[i])
out<<nod<<" ";
out<<endl;
}
}