Pagini recente » Cod sursa (job #1908430) | Cod sursa (job #742243) | Cod sursa (job #1274349) | Cod sursa (job #3123991) | Cod sursa (job #1970963)
#include <vector>
#include <fstream>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <set>
#include <stack>
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 tata[MAXN]; // tatal din arborele DFS
bool viz[MAXN];
bool este[MAXN]; // Este punct de articulatie?
int componente;
set<int>comp[MAXN];
int timp;
stack<pair<int, int>>st;
ifstream in("biconex.in");
ofstream out("biconex.out");
void citire(){
in>>n>>m;
int a, b;
while(m--){
in>>a>>b;
graf[a].push_back(b);
graf[b].push_back(a);
}
}
void dfs(int nod){
viz[nod] = 1;
++timp;
low[nod] = t[nod] = timp;
int copii = 0; // numarul de fii din arborele DFS
for(auto fiu : graf[nod]){
if(!viz[fiu]){
++copii;
tata[fiu] = nod;
st.push(make_pair(nod, fiu));
dfs(fiu);
low[nod] = min(low[nod], low[fiu]);
if(tata[nod] == -1 && copii >= 2){
//Cazul 1: Daca este radacina arborelui DFS si are cel putin 2 fii
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(st.top().first);
comp[componente].insert(st.top().second);
st.pop();
++componente;
}
if(tata[nod] != -1 && low[fiu] >= t[nod]){
//Cazul 2: Daca nu este radacina, insa are cel putin 2 fii independenti
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(st.top().first);
comp[componente].insert(st.top().second);
st.pop();
++componente;
}
} else if(fiu != tata[nod]) {
low[nod] = min(low[nod], t[fiu]);
st.push(make_pair(nod, fiu));
}
}
}
int main(){
citire();
memset(tata, -1, sizeof(tata));
for(int nod = 1; nod <= n ; ++nod){
if(!viz[nod])
dfs(nod);
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;
}
}
out<<componente<<'\n';
for(int i = 0; i < componente; i++){
for(auto it = comp[i].begin(); it != comp[i].end(); ++it)
out<<*it<<' ';
out<<'\n';
}
}