Pagini recente » Cod sursa (job #304138) | Cod sursa (job #2449760) | Cod sursa (job #369030) | Cod sursa (job #1404435) | Cod sursa (job #1329213)
#include<fstream>
#include<vector>
#include<stack>
#include<utility>
#define MAXN 100001
using namespace std;
typedef int var;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
stack<pair<var, var> >ST;
vector<var> G[MAXN];
var PARENT[MAXN], D[MAXN], LOW[MAXN];
vector<var> CBC[MAXN];
bool VIZ[MAXN];
var n;
var time, cbc;
void dfs(var node) {
VIZ[node] = 1;
D[node] = ++time;
LOW[node] = D[node];
for(vector<var>::iterator it = G[node].begin(); it != G[node].end(); ++it) {
const var &vec = *it;
if(vec == PARENT[node]) continue;
if(!VIZ[vec]) {
VIZ[vec] = 1;
PARENT[vec] = node;
ST.push(make_pair(node, vec));
dfs(vec);
LOW[node] = min(LOW[node], LOW[vec]);
if(LOW[vec] >= D[node]) {
cbc++;
CBC[cbc].push_back(ST.top().second);
while(ST.top() != make_pair(PARENT[node], node)) {
CBC[cbc].push_back(ST.top().first);
ST.pop();
}
}
} else if(LOW[vec] < LOW[node]) {
LOW[node] = LOW[vec];
}
}
}
int main() {
var m, a, b;
fin>>n>>m;
for(var i=1; i<=m; i++) {
fin>>a>>b;
G[a].push_back(b);
G[b].push_back(a);
}
ST.push(make_pair(0, 1));
for(var i=1; i<=n; i++) {
if(!VIZ[i]) {
dfs(i);
}
}
fout<<cbc<<'\n';
for(var i=1; i<=cbc; ++i) {
for(vector<var>::iterator it = CBC[i].begin(); it != CBC[i].end(); ++it) {
fout<<*it<<" ";
}
fout<<'\n';
}
return 0;
}