Pagini recente » Cod sursa (job #3031629) | Cod sursa (job #743482) | Cod sursa (job #2690755) | Cod sursa (job #1334791) | Cod sursa (job #1384586)
#include <iostream>
#include <fstream>
#include <vector>
#include <list>
#include <stack>
#include <algorithm>
#define MAX 200000
using namespace std;
int lowest[MAX], dist[MAX];
stack<pair<int, int> > edges;
vector<list<int> > graph;
vector<vector<int> > sol;
void read()
{
ifstream f("biconex.in");
int i, j;
f >> i >> j;
graph.resize(i+1);
while (f >> i && f >> j)
{
graph[i].push_back(j);
graph[j].push_back(i);
}
f.close();
}
void DFS(int node, int parent)
{
lowest[node] = dist[node] = dist[parent] + 1;
for (list<int>::iterator i = graph[node].begin(); i != graph[node].end(); ++i)
{
int adj = *i;
if (adj == parent) continue;
if (dist[adj] == -1)
{
edges.push(make_pair(node, adj));
DFS(adj, node);
lowest[node] = min(lowest[node], lowest[adj]);
if (lowest[adj] >= dist[node])
{
vector<int> solVector;
while (!edges.empty())
{
solVector.push_back(edges.top().first);
solVector.push_back(edges.top().second);
if (edges.top().first == node && edges.top().second == adj)
{
edges.pop();
break;
}
edges.pop();
}
sort(solVector.begin(), solVector.end());
for (vector<int>::iterator j = solVector.begin(); j != solVector.end() - 1; ++j)
{
if (*j == *(j+1))
{
solVector.erase(j);
--j;
}
}
sol.push_back(solVector);
}
}
else
lowest[node] = min(lowest[node], lowest[adj]);
}
}
void write()
{
ofstream f("biconex.out");
f << sol.size() << "\n";
for (vector<vector<int> >::iterator i = sol.begin(); i != sol.end(); ++i)
{
for (vector<int>::iterator j = i->begin(); j != i->end(); ++j)
f << *j << " ";
f << "\n";
}
f.close();
}
int main()
{
read();
for (int i = 0; i < MAX; ++i) dist[i] = -1;
DFS(1, 0);
write();
return 0;
}