Pagini recente » Cod sursa (job #2151058) | Cod sursa (job #2000656) | Cod sursa (job #1926879) | Cod sursa (job #974214) | Cod sursa (job #1922443)
#include <list>
#include <fstream>
#include <set>
#include <algorithm>
#include <stack>
#include <vector>
using namespace std;
ifstream ka("biconex.in");
ofstream ki("biconex.out");
int* ciclu_min;
int* nivel;
list<int> *graf;
vector<int> *solutie;
bool* vizitat;
stack< pair<int, int> >stiva;
int cate;
void DFS(int t)
{
vizitat[t] = true;
ciclu_min[t] = nivel[t];
for(list<int>::iterator it = graf[t].begin(); it != graf[t].end(); ++it)
{
if(vizitat[*it] == false)
{
nivel[*it] = nivel[t] + 1;
stiva.push(make_pair(t, *it));
DFS(*it);
ciclu_min[t] = min(ciclu_min[t], ciclu_min[*it]);
if(ciclu_min[*it] >= nivel[t])
{
cate++;
while(!stiva.empty() && (stiva.top().first != t || stiva.top().second != *it))
{
solutie[cate].push_back(stiva.top().first);
solutie[cate].push_back(stiva.top().second);
stiva.pop();
}
if(!stiva.empty())
{
solutie[cate].push_back(t);
solutie[cate].push_back(*it);
stiva.pop();
}
}
}
else if(nivel[*it] < nivel[t] - 1)
ciclu_min[t] = min(ciclu_min[t], nivel[*it]);
}
}
int main()
{
int n, m;
ka >> n >> m;
ciclu_min = new int[n + 1];
nivel = new int[n + 1];
vizitat = new bool[n + 1];
graf = new list<int>[n + 1];
solutie = new vector<int>[n + 1];
for(int i = 1; i <= n; i++)
vizitat[i] = false;
for(int i = 1; i <= m; i++)
{
int x, y;
ka >> x >> y;
graf[x].push_back(y);
graf[y].push_back(x);
}
nivel[1] = 1;
DFS(1);
ki << cate << '\n';
for(int i = 1; i <= cate; i++)
{
sort(solutie[i].begin(), solutie[i].end());
ki << solutie[i][0] << " ";
for(int j = 1; j < solutie[i].size(); j++)
if(solutie[i][j] != solutie[i][j - 1])
ki << solutie[i][j] << " ";
ki << '\n';
}
}