Pagini recente » Cod sursa (job #1364826) | Cod sursa (job #1846863) | Cod sursa (job #767735) | Cod sursa (job #610534) | Cod sursa (job #3331813)
#include <fstream>
#include <queue>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <map>
#include <unordered_map>
#include <string>
#include <unordered_set>
#include <set>
#include <stack>
#include <climits>
#include <iomanip>
#include <bitset>
using namespace std;
ifstream cin("biconex.in");
ofstream cout("biconex.out");
const int NMAX = 1e5+5;
const int MOD = 1e9+7;
const int INF = (1 << 30);
using ld = long double;
using ull = unsigned long long;
using ll = long long;
using ui = unsigned int;
using pii = pair<int, int>;
int n,m,t,indEdges,indBcc;
vector<int> graf[NMAX];
int low[NMAX];
int dfsTime[NMAX];
pii edges[NMAX];
unordered_set<int> bcc[NMAX];
void GetBCC(pii rootEdge) {
indBcc++;
while (edges[indEdges]!=rootEdge) {
bcc[indBcc].insert(edges[indEdges].first);
bcc[indBcc].insert(edges[indEdges].second);
indEdges--;
}
bcc[indBcc].insert(edges[indEdges].first);
bcc[indBcc].insert(edges[indEdges].second);
indEdges--;
}
void dfs(int node,int dad) {
dfsTime[node]=low[node]=++t;
for (auto &vecin:graf[node]) {
if (vecin!=dad && dfsTime[vecin]<dfsTime[node]) {
edges[++indEdges]={node,vecin};
}
if (!low[vecin]) {
dfs(vecin,node);
low[node]=min(low[node],low[vecin]);
if (low[vecin]>=dfsTime[node]) GetBCC({node,vecin});
}
else if (vecin!=dad) low[node]=min(low[node],dfsTime[vecin]);
}
}
void solve() {
cin>>n>>m;
for (int i=1;i<=m;i++) {
int x,y;
cin>>x>>y;
graf[x].push_back(y);
graf[y].push_back(x);
}
for (int i=1;i<=n;i++) {
if (!low[i]) dfs(i,0);
}
cout<<indBcc<<"\n";
for (int i=1;i<=indBcc;i++,cout<<"\n") {
for (auto &node:bcc[i]) cout<<node<<" ";
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
solve();
return 0;
}