Pagini recente » Cod sursa (job #2194673) | Cod sursa (job #1204273) | Cod sursa (job #1764276) | Cod sursa (job #2269575) | Cod sursa (job #2663424)
#include <bits/stdc++.h>
using namespace std;
using pii = pair <int, int>;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
vector < vector <int> > g;
vector <int> lowlink, depth;
vector < set <int> > comps;
int V, E;
stack <pii> Stack;
void readData(){
fin >> V >> E;
g.resize(V + 1);
lowlink.resize(V + 1);
depth.resize(V + 1);
comps.reserve(V);
for(int e = 0; e < E; ++e){
int u, v;
fin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
}
void cacheBC(const pii &edge){
pii stackEdge;
set <int> BC;
do{
stackEdge = Stack.top();
Stack.pop();
BC.insert(stackEdge.first);
BC.insert(stackEdge.second);
}while(stackEdge != edge);
comps.push_back(BC);
}
void DFS(int node, int dad, int d){
depth[node] = lowlink[node] = d;
for(const int &adj : g[node])
if(adj != dad){
if(depth[adj] == 0){
Stack.push({node, adj});
DFS(adj, node, d + 1);
lowlink[node] = min(lowlink[node], lowlink[adj]);
if(lowlink[adj] >= depth[node])
cacheBC({node, adj});
}
else lowlink[node] = min(lowlink[node], depth[adj]);
}
}
int main(){
readData();
for(int node = 1; node <= V; ++node) // even though it is connected
if(depth[node] == 0)
DFS(node, 0, 1);
// printing
comps.resize(comps.size());
fout << comps.size() << '\n';
for(int c = 0; c < (int)comps.size(); ++c){
for(const int &node : comps[c])
fout << node << ' ';
fout << '\n';
}
}