Pagini recente » Cod sursa (job #3277789) | TVShow | Arhiva de probleme | Profil muresan_sabina | Cod sursa (job #3287566)
#include <fstream>
#include <vector>
#include <stack>
#include <set>
using namespace std;
ifstream cin("biconex.in");
ofstream cout("biconex.out");
vector<int> G[100005] , biconexe[100005];
///vector<pair<int,int>> sol;
stack<int> stiva;
///set<int> s;
int v[105];
int low[105] , num[105];
int timpulamea , n , m , k;
void citire()
{
int x , y;
cin >> n >> m ;
for(int i = 1 ; i<=m ; ++i)
{
cin >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
}
void dfs(int nod , int rad )
{
v[nod] = 1;
low[nod] = num[nod] = ++timpulamea;
stiva.push(nod);
for(auto e : G[nod])
if(e != rad)
{
if(!v[e])
{
dfs(e,nod);
if(low[e] <= low[nod])
low[nod] = low[e];
else
{
///s.insert(nod);
///s.insert(e);
++k;
biconexe[k].push_back(nod);
biconexe[k].push_back(e);
///sol.push_back({nod,e});
}
}
else if(low[e] <= low[nod])
low[nod] = low[e];
}
if(low[nod] == num[nod])
{
if(stiva.top() != nod && !stiva.empty())
{
++k;
while(!stiva.empty() && low[stiva.top()] == low[nod])
{
biconexe[k].push_back(stiva.top());
stiva.pop();
}
}
else if(!stiva.empty())
stiva.pop();
}
}
void debug()
{
cout << "****** GRAF ******\n";
for(int i = 1 ; i<=n ; ++i)
{
cout << "Pentru " << i << " : ";
for(auto e : G[i]) cout << e << ' ';
cout << '\n';
}
cout << "\n\n";
cout << "****** BICONEXE ******\n";
for(int i = 1 ; i<=k ; ++i)
{
cout << "Pentru " << i << " : ";
for(auto e : biconexe[i]) cout << e << ' ';
cout << '\n';
}
}
int main()
{
citire();
dfs(1,0);
///debug();
cout << k << '\n';
for(int i = 1 ; i<=k ; ++i)
{
for(auto e : biconexe[i]) cout << e << ' ';
cout << '\n';
}
}