Pagini recente » Cod sursa (job #1681987) | Cod sursa (job #1541349) | Cod sursa (job #2738597) | Cod sursa (job #1705611) | Cod sursa (job #581839)
Cod sursa(job #581839)
#include <fstream>
#include <vector>
#include <deque>
#include <algorithm>
using namespace std;
ifstream in("biconex.in");
ofstream out("biconex.out");
struct edge{
int a, b;
};
const int N = 100001;
int n;
int biCount;
int fat[N];
int h[N];
int up[N];
bool vis[N];
vector <int> g[N];
vector <int> b[N];
deque <edge> e;
void Read()
{
int n, m;
in >> n >> m;
while (m--)
{
int a, b;
in >> a >> b;
g[a].push_back(b);
g[b].push_back(a);
}
}
void DiggIn(int node)
{
vis[node] = true;
up[node] = h[node];
for (int i = 0; i < g[node].size(); ++i)
{
int next = g[node][i];
if (!vis[next])
{
edge curEdge;
curEdge.a = node;
curEdge.b = next;
e.push_back(curEdge);
fat[next] = node;
h[next] = h[node] + 1;
DiggIn(next);
if (up[next] < up[node])
up[node] = up[next];
if (up[next] >= h[node])
{
++biCount;
curEdge = e.back();
while (curEdge.a != node || curEdge.b != next)
{
b[biCount].push_back(curEdge.a);
b[biCount].push_back(curEdge.b);
e.pop_back();
curEdge = e.back();
}
b[biCount].push_back(curEdge.a);
b[biCount].push_back(curEdge.b);
e.pop_back();
}
}
else if (fat[node] != next && h[next] < h[node])
{
if (up[node] > h[next])
up[node] = h[next];
edge curEdge;
curEdge.a = node;
curEdge.b = next;
e.push_back(curEdge);
}
}
}
void Print()
{
out << biCount << "\n";
for (int i = 1; i <= biCount; ++i)
{
sort(b[i].begin(), b[i].end());
b[i].resize( unique(b[i].begin(), b[i].end()) - b[i].begin());
for (int j = 0; j < b[i].size(); ++j)
out << b[i][j] << " ";
out << "\n";
}
}
int main()
{
Read();
DiggIn(1);
Print();
return 0;
}