Pagini recente » Cod sursa (job #780914) | Cod sursa (job #1143566) | Cod sursa (job #698596) | Cod sursa (job #836890) | Cod sursa (job #2797976)
#include<bits/stdc++.h>
using namespace std;
ifstream fin ("biconex.in");
ofstream fout ("biconex.out");
vector<int> lista_adiacenta[100001];
unordered_map<int,int> vizitat;
vector <set <int>> componente;
stack<pair<int, int>> stackCBC;
int low[100001]= {0};
int timp,elem1,elem2;
void biconex(int start, int tata)
{
timp++;
vizitat[start] = timp;
low[start] = timp;
for (int i=0; i<lista_adiacenta[start].size(); i++)
{
//if(vizitat[lista_adiacenta[start][i]]!=tata)
//{
if (vizitat[lista_adiacenta[start][i]]==0)
{
stackCBC.push({start, lista_adiacenta[start][i]});
biconex(lista_adiacenta[start][i],start);
if(low[start]>=low[lista_adiacenta[start][i]]) low[start] = min(low[lista_adiacenta[start][i]],low[start]);
if (low[lista_adiacenta[start][i]]>=vizitat[start])
{
set<int> elem;
elem1 = stackCBC.top().first;
elem2 = stackCBC.top().second;
elem.insert(elem1);
elem.insert(elem2);
stackCBC.pop();
while (elem1 != start || elem2 != lista_adiacenta[start][i])
{
elem1 = stackCBC.top().first;
elem2 = stackCBC.top().second;
elem.insert(elem1);
elem.insert(elem2);
stackCBC.pop();
}
componente.push_back(elem);
}
}
else if(low[start]>=low[lista_adiacenta[start][i]])
{
low[start] = min(vizitat[lista_adiacenta[start][i]],low[start]);
}
//}
}
}
int main()
{
int n,m,x,y;
ios_base::sync_with_stdio(false);
fin.tie(NULL);
fout.tie(NULL);
fin>>n>>m;
for(int i=1; i<=m; i++)
{
fin>>x>>y;
lista_adiacenta[x].push_back(y);
lista_adiacenta[y].push_back(x);
}
biconex(1,0);
fout<< componente.size() <<'\n';
for (auto cbc: componente)
{
set<int>::iterator it;
for (it = cbc.begin(); it != cbc.end(); it++)
fout << *it << " ";
fout << "\n";
}
return 0;
}