Pagini recente » Cod sursa (job #1275919) | Monitorul de evaluare | Istoria paginii runda/testere | Cod sursa (job #2725926) | Cod sursa (job #1998164)
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <ctime>
#include <algorithm>
#include <stack>
#include <vector>
using namespace std;
ifstream in("biconex.in");
ofstream out("biconex.out");
#define ll long long
#define pb push_back
const int inf = 1e9 + 5;
const int NMax = 1e5 + 5;
int N,M,nrComp;
int depth[NMax],lowPoint[NMax];
vector<int> v[NMax];
vector<int> comp[NMax];
struct elem {
int x,y;
elem(int _x = 0,int _y = 0) {
x = _x;
y = _y;
}
};
bool operator ==(elem a,elem b) {
return (a.x == b.x && a.y == b.y);
}
stack<elem> st;
void dfs(int,int);
void getComp(elem);
int main() {
in>>N>>M;
while (M--) {
int x,y;
in>>x>>y;
v[x].pb(y);
v[y].pb(x);
}
dfs(1,0);
out<<nrComp<<'\n';
for (int i=1;i <= nrComp;++i) {
for (int e : comp[i]) {
out<<e<<' ';
}
out<<'\n';
}
in.close();out.close();
return 0;
}
void dfs(int node,int dad) {
lowPoint[node] = depth[node] = depth[dad] + 1;
st.push(elem(dad,node));
for (int nxt : v[node]) {
if (depth[nxt]) {
lowPoint[node] = min(lowPoint[node],depth[nxt]);
continue;
}
dfs(nxt,node);
lowPoint[node] = min(lowPoint[node],lowPoint[nxt]);
if (lowPoint[nxt] == depth[node]) {
getComp(elem(node,nxt));
}
}
}
void getComp(elem first) {
++nrComp;
while (!(st.top() == first)) {
comp[nrComp].pb(st.top().y);
st.pop();
}
comp[nrComp].pb(first.y);
comp[nrComp].pb(first.x);
st.pop();
}