Pagini recente » Cod sursa (job #842117) | Cod sursa (job #2897488) | Cod sursa (job #299760) | Cod sursa (job #2032148) | Cod sursa (job #2781445)
#include <bits/stdc++.h>
#include <fstream>
#define VMAX 100000
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
vector <int> adj[VMAX];
int V, E, x, timp, y;
int disc[VMAX], low[VMAX];
bool artPoint[VMAX];
stack < pair <int, int> > edges;
vector < unordered_set <int> > allBcc(VMAX);
int nrBcc;
void DFSap(int u, int parent = -1)
{
int children = 0;
disc[u] = low[u] = ++timp;
for (auto w : adj[u])
{
if (parent == w) continue;
if (!disc[w])
{
edges.push(make_pair(u, w));
DFSap(w, u);
low[u] = min(low[u], low[w]);
if (low[w] >= disc[u])
{
while (edges.top() != make_pair(u, w))
{
allBcc[nrBcc].insert(edges.top().first);
allBcc[nrBcc].insert(edges.top().second);
edges.pop();
}
allBcc[nrBcc].insert(edges.top().first);
allBcc[nrBcc].insert(edges.top().second);
edges.pop();
nrBcc++;
}
}
else if (disc[w] < disc[u])
{
edges.push(make_pair(u, w));
low[u] = min(low[u], disc[w]);
}
}
}
int main()
{
fin >> V >> E;
while (E--)
{
fin >> x >> y;
x--, y--;
adj[x].push_back(y);
adj[y].push_back(x);
}
for (int i = 0; i < V; ++i)
{
if (!disc[i]) DFSap(i);
timp = 0;
}
fout << nrBcc << endl;
for (int i = 0; i < V; ++i)
{
bool ok = false;
for (auto j : allBcc[i])
{
ok = true;
fout << j + 1 << " ";
}
if (ok) fout << endl;
}
fin.close();
fout.close();
return 0;
}
/*
5 5
0 2
1 2
1 0
0 3
3 4
*/
/*
5 6
1 2
2 3
1 3
3 4
4 5
5 3
*/
/*
8 9
1 2
2 3
3 4
4 1
1 5
5 6
6 7
7 5
7 8
*/