Pagini recente » Cod sursa (job #3313329) | Cod sursa (job #3347140) | Cod sursa (job #1000170) | Cod sursa (job #3336998) | Cod sursa (job #3342918)
#include <fstream>
#include <vector>
#include <set>
#include <stack>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
const int Nmax = 200005;
struct nod{
int timp_initial, timp_atins, nr_componenta;
vector<int> vecini;
};
int n, m, timp, nr_componenta;
nod graf[Nmax];
stack<pair<int, int>> st;
set<int> componente[Nmax];
void citire(){
int nod1, nod2;
fin >> n >> m;
for(int i = 1; i <= m; i++){
fin >> nod1 >> nod2;
graf[nod1].vecini.push_back(nod2);
graf[nod2].vecini.push_back(nod1);
}
}
void dfs_tarjan(int nod, int parinte){
graf[nod].timp_initial = graf[nod].timp_atins = ++timp;
for(int vecin : graf[nod].vecini){
if(!graf[vecin].timp_initial){
st.push({nod, vecin});
dfs_tarjan(vecin, nod);
graf[nod].timp_atins = min(graf[nod].timp_atins, graf[vecin].timp_atins);
if(graf[vecin].timp_atins >= graf[nod].timp_initial){
nr_componenta++;
while(st.top().first != nod || st.top().second != vecin){
componente[nr_componenta].insert(st.top().first);
componente[nr_componenta].insert(st.top().second);
st.pop();
}
componente[nr_componenta].insert(nod);
componente[nr_componenta].insert(vecin);
st.pop();
}
}
else if(vecin != parinte){
if(graf[vecin].timp_initial < graf[nod].timp_initial){
graf[nod].timp_atins = min(graf[nod].timp_atins, graf[vecin].timp_initial);
st.push({nod,vecin});
}
}
}
}
void afisare(){
fout << nr_componenta << '\n';
for(int i = 1; i <= nr_componenta; i++){
for(int nod : componente[i]){
fout << nod << ' ';
}
fout << '\n';
}
}
int main(){
citire();
dfs_tarjan(1, 0);
afisare();
return 0;
}