Pagini recente » Cod sursa (job #492011) | Cod sursa (job #182014) | Cod sursa (job #878404) | Cod sursa (job #1676176) | Cod sursa (job #1572216)
/*
*/
#include <algorithm>
#include <fstream>
#include <cstring>
#include <vector>
#include <stack>
using namespace std;
ifstream is ("biconex.in");
ofstream os ("biconex.out");
const int Nmax = 100001;
using PII = pair<int,int>;
int N, M;
vector <int> Graph[Nmax];
stack <PII> S; //tata si fiu
vector <vector<int> > BCCs;
int TreeEdgesFromRoot, BackEdges;
int Link[Nmax], Depth[Nmax], F[Nmax];
bool Viz[Nmax];
void DFS(int x, int d);
void Extract(int x, int y);
int main()
{
is >> N >> M;
for (int a, b; M; --M)
{
is >> a >> b;
Graph[a].push_back(b);
Graph[b].push_back(a);
}
DFS(1, 1);
os << BCCs.size() << '\n';
for (auto& BC : BCCs)
{
sort(BC.begin(), BC.end());
for (const int& x : BC)
os << x << ' ';
os << '\n';
}
is.close();
os.close();
}
void DFS(int x, int d)
{
Depth[x] = Link[x] = d;
Viz[x] = 1;
if (d == 2)
TreeEdgesFromRoot++;
for (const int& y : Graph[x])
{
if (y == F[x]) continue; //daca e tata, sarim peste
if (Viz[y] == 0) //treeedge
{
S.push({x, y});
F[y] = x;
DFS(y, d+1);
Link[x] = min(Link[x], Link[y]);
if (Link[y] >= Depth[x]) //critic
Extract(x, y);
}
else //backedge
Link[x] = min(Link[x], Depth[y]);
}
};
void Extract(int x, int y)
{
vector <int> C;
int X, Y;
do
{
X = S.top().first;
Y = S.top().second;
S.pop();
C.push_back(Y);
}
while (X != x && Y != y && !S.empty());
C.push_back(x);
BCCs.push_back(C);
};