Pagini recente » Cod sursa (job #3340203) | Cod sursa (job #3339729) | Cod sursa (job #3334862) | Cod sursa (job #2321822) | Cod sursa (job #3323136)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream fin ("biconexe.in");
ofstream fout("biconexe.out");
vector<vector<int>> graf;
vector<int> viz;
vector<int> timp;
vector<int> low;
vector<int> tata, art;
stack<pair<int, int>> st;
vector<vector<pair<int, int>>> bicon;
int N, M;
void dfs(int x, int& contor, int& nr)
{
viz[x] = 1;
int copii = 0;
for(auto& i : graf[x])
{
if(viz[i] == 0)
{
st.push({x, i});
tata[i] = x;
copii++; // numar cati copii are nodul curent
timp[i] = ++contor;
low[i] = contor;
dfs(i, contor, nr);
low[x] = min(low[x], low[i]);
if(low[i] >= timp[x])
{
nr++; // am gasit o componenta biconexa
bicon.push_back(vector<pair<int,int>>());
while(!st.empty())
{
pair<int, int> vf = st.top();
bicon.back().push_back(vf);
st.pop();
if ((vf.first == x && vf.second == i) || (vf.first == i && vf.second == x))
break;
}
}
}
else if(tata[x] != i)
{
st.push({x, i});
low[x] = min(low[x], timp[i]);
}
}
}
int main()
{
fin>>N>>M;
int nr = 0; // nr de compenente biconexe
graf.assign(N+1, {}); // {} -> graf gol
viz.assign(N+1, 0);
timp.assign(N+1, 0);
low.assign(N+1, 0);
tata.assign(N+1, 0);
art.assign(N+1, 0);
for(int i=1; i<=M; i++)
{
int x,y;
fin>>x>>y;
graf[x].push_back(y);
graf[y].push_back(x);
}
int contor = 1;
for(int i=1; i<=N; i++)
if(viz[i] == 0)
{
timp[i] = contor;
low[i] = contor;
dfs(i, contor, nr);
}
cout << nr << "\n";
for (int j = 0; j < nr; j++)
{
vector<int> noduri;
vector<int> apare(N + 1, 0);
// extrag nodurile fără duplicate
for (auto &m : bicon[j])
{
if (!apare[m.first])
{
apare[m.first] = 1;
noduri.push_back(m.first);
}
if (!apare[m.second])
{
apare[m.second] = 1;
noduri.push_back(m.second);
}
}
// afișez nodurile componentei biconexe
for (int x : noduri)
cout << x << " ";
cout << "\n";
}
/*
/// aici numaram cate puncte de articulatie am, pt alta problema
for(int i=1; i<art.size(); i++)
nr += art[i];
cout<<nr<<endl;
*/
return 0;
}
/*void bfs(int x, int& ok)
{
viz[x] = 1;
culoare[x] = 1;
while(!coada.empty())
{
for(auto &i : graf[x])
{
if(viz[i] == 1)
{
if(culoare[x] == culoare[i])
ok = 0;
}
if(viz[i] == 0)
{
viz[i] = 1;
coada.push(i);
if(culoare[x] == 1)
culoare[i] = 2;
else culoare[i] = 1;
}
}
coada.pop();
if(!coada.empty())
x = coada.front();
}
}*/