Pagini recente » Cod sursa (job #1137781) | Cod sursa (job #2503416) | Cod sursa (job #2873966) | Cod sursa (job #2930332) | Cod sursa (job #1971125)
#include <vector>
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <set>
#include <stack>
#include <bitset>
using namespace std;
const int MAXN = 100005;
vector<int>graf[MAXN];
int n, m;
int t[MAXN]; // momentul cand a fost vizitat nodul
int low[MAXN]; // minimul dintre momentul tatalui si momentul nodului
int componente;
set<int>comp[MAXN];
int timp;
stack<pair<int, int>>st;
bitset<MAXN> este;
int viz[MAXN];
void citire(){
freopen("biconex.in", "r", stdin);
freopen("biconex.out", "w", stdout);
scanf("%d %d", &n, &m);
int a, b;
while(m--){
scanf("%d %d", &a, &b);
graf[a].push_back(b);
graf[b].push_back(a);
}
}
void dfs(int nod, int tata){
++timp;
low[nod] = t[nod] = timp;
int copii = 0;
for(auto fiu : graf[nod]){
if(t[fiu] == -1){
++copii;
st.push(make_pair(nod, fiu));
dfs(fiu, nod);
low[nod] = min(low[nod], low[fiu]);
if((tata == -1 && copii >= 2) || tata != -1 && low[fiu] >= t[nod]){
este[nod] = 1;
while(st.top().first != nod && st.top().second != fiu){
comp[componente].insert(st.top().first);
comp[componente].insert(st.top().second);
st.pop();
}
comp[componente].insert(nod);
comp[componente].insert(fiu);
st.pop();
++componente;
}
} else if(fiu != tata) {
low[nod] = min(low[nod], t[fiu]);
st.push(make_pair(nod, fiu));
}
}
}
int main(){
citire();
memset(t, -1, sizeof(t));
for(int nod = 1; nod <= n ; ++nod){
if(t[nod] == -1)
dfs(nod, -1);
bool isempty = 1;
while(!st.empty()){
isempty = 0;
comp[componente].insert(st.top().first);
comp[componente].insert(st.top().second);
st.pop();
}
if(!isempty){
++componente;
}
}
printf("%d\n", componente);
for(int i = 0; i < componente; i++){
for(auto it : comp[i]){
if(!viz[it]){
viz[it]++;
printf("%d ", it);
}
else if(viz[it] < graf[it].size() && este[it]){
printf("%d ", it);
viz[it]++;
}
}
printf("\n");
}
}