Pagini recente » Cod sursa (job #3308218) | Cod sursa (job #2767975) | Cod sursa (job #66272) | Cod sursa (job #3322044) | Cod sursa (job #3332479)
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <string>
#include <set>
#include <queue>
#include <stack>
int n, m, idx[1001], low[1001];
bool estePunct[1001]={false};
std::vector<int>v[1001];
std::stack<std::pair<int, int>>sta;
int ceas;
void Tarjan_PDA(int nod, int tata){
int i, e, s, cont=0, nr_copii=0;
idx[nod]=low[nod]=++ceas;
for(const auto element:v[nod]){
if(element==tata)continue;
else{
if(idx[element]==0){
nr_copii++;
sta.push({nod, element});
Tarjan_PDA(element, nod);
low[nod]=std::min(low[nod], low[element]);
if(low[element]>=idx[nod]){
if(tata!=-1)estePunct[nod]=true;
std::vector<int> noduri_componenta;
bool viz_local[1001]={false};
while(true){
std::pair<int, int> muchie = sta.top();
sta.pop();
if (!viz_local[muchie.first]) {
noduri_componenta.push_back(muchie.first);
viz_local[muchie.first] = true;
}
if (!viz_local[muchie.second]) {
noduri_componenta.push_back(muchie.second);
viz_local[muchie.second] = true;
}
if(muchie.first==nod && muchie.second==element)break;
}
std::cout << "Componenta : ";
for(int ele :noduri_componenta)
std::cout << ele << " ";
std::cout << "\n";
}
}
else{
if(element!=tata && idx[element] < idx[nod]){
sta.push({nod, element});
}
if(idx[element]!=0){
low[nod]=std::min(low[nod], idx[element]);
}
}
}
}
if(tata==-1 && nr_copii>1)estePunct[nod]=true;
}
int main(){
int i, e, s, cont=0, a, b, nr_puncte=0;
std::cin >> n >> m;
for(i=1; i<=m; ++i){
std::cin >> a >> b;
v[a].push_back(b);
v[b].push_back(a);
}
for(i=1; i<=n; ++i)
{
if(idx[i]==0){
Tarjan_PDA(i, -1);
}
}
for(i=1; i<=n; ++i)
if(estePunct[i]==true)std::cout << i << " ";
std::cout << "\n";
return 0;
}