Pagini recente » Cod sursa (job #2803166) | Cod sursa (job #2853950) | Cod sursa (job #2635072) | Cod sursa (job #3224195) | Cod sursa (job #2176359)
#include <fstream>
#include <vector>
#include <algorithm>
#include <set>
#include <stack>
#define Nmax 100009
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
typedef pair <int, int> edge;
#define x first
#define y second
int n,m,x,y,low[Nmax],found[Nmax],cnt,parent[Nmax];
vector <int> G[Nmax],v,sol;
vector <vector <int>> BiconexComponents;
stack <edge> S;
void ReadInput() {
f>>n>>m;
for (int i=1; i<=m; ++i) {
f>>x>>y;
G[x].push_back(y);
G[y].push_back(x);
}
}
void getBCC(edge E) {
edge aux;
v.clear();
do {
aux=S.top();
S.pop();
// g<<aux.x<<' '<<aux.y<<'\n';
v.push_back(aux.x);
v.push_back(aux.y);
} while (aux!=E);
sort(v.begin(), v.end());
auto it = unique(v.begin(), v.end());
v.erase(it, v.end());
BiconexComponents.push_back(v);
}
void DFS(int node) {
++cnt;
found[node]=cnt;
low[node]=cnt;
for (auto x: G[node]) {
if (!parent[x]) {
S.push(edge(node,x));
parent[x]=node;
DFS(x);
low[node]=min(low[node],low[x]);
if (low[x]>=found[node]) getBCC(edge(node,x));
}
else if (parent[node]!=x) low[node]=min(low[node],found[x]);
}
}
void Tarjan() {
for (int i=1; i<=n; ++i)
if (!parent[i]) {
parent[i]=i;
DFS(i);
}
/*for (int i=1; i<=n; ++i) g<<found[i]<<' ';
g<<'\n';
for (int i=1; i<=n; ++i) g<<low[i]<<' ';
g<<'\n';
for (int i=1; i<=n; ++i) g<<parent[i]<<' ';
g<<'\n';*/
}
void WriteOutput() {
g<<BiconexComponents.size()<<'\n';
for (auto x: BiconexComponents) {
for (auto y: x) g<<y<<' ';
g<<'\n';
}
}
void Solve() {
Tarjan();
}
int main() {
ReadInput();
Solve();
WriteOutput();
f.close(); g.close();
return 0;
}