Pagini recente » Cod sursa (job #3140395) | Cod sursa (job #2961812) | Cod sursa (job #3260661) | Cod sursa (job #2686047) | Cod sursa (job #2664885)
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int NMAX = 1e5;
// ---------- CITIRE ------------
vector <int> g[1 + NMAX];
int n, m;
void citire() {
scanf("%d%d", &n, &m);
for(int i = 0; i < m; i ++) {
int u, v;
scanf("%d%d", &u, &v);
g[u].push_back(v);
g[v].push_back(u);
}
}
// ---------- REZOLVARE ---------
int currentTime, dfsRoot, rootsNumberOfChildren, numberOfAP;
int discoverTime[1 + NMAX], lowLink[1 + NMAX], dfsParent[1 + NMAX];
bool isArticulationPoint[1 + NMAX];
void ArticulationPointsDFS(int from) {
discoverTime[from] = lowLink[from] = ++currentTime;
for(auto &to: g[from]) {
if(discoverTime[to] == 0) {
dfsParent[to] = from;
if(from == dfsRoot) ++rootsNumberOfChildren;
ArticulationPointsDFS(to);
if(isArticulationPoint[from] == false && lowLink[to] >= discoverTime[from]) {
isArticulationPoint[from] = true;
numberOfAP ++; /// De verificat repetitii, da am trebuie verificat
}
lowLink[from] = min(lowLink[from], lowLink[to]);
} else {
/// De repetat asta
if(to != dfsParent[from])
lowLink[from] = min(lowLink[from], lowLink[to]);
}
}
}
void solve() {
for(int i = 1; i <= n; i ++) {
if(discoverTime[i] == 0) {
dfsRoot = i;
rootsNumberOfChildren = 0;
ArticulationPointsDFS(dfsRoot);
if(isArticulationPoint[dfsRoot] == false && rootsNumberOfChildren > 1) {
numberOfAP ++; /// Si aici aveam repetitii
isArticulationPoint[dfsRoot] = true;
}
}
}
}
// ---------- AFISARE -----------
bool visited[1 + NMAX];
void dfsAfisare(int from) {
printf("%d ", from);
visited[from] = true;
for(auto &to : g[from]) {
if(visited[to] == false && isArticulationPoint[to] == false) {
dfsAfisare(to);
}
}
}
void afisare() {
printf("%d\n", numberOfAP + 1);
for(int i = 1; i <= n; i ++) {
if(isArticulationPoint[i] == true) {
// dfsAfisare(i);
// printf("\n");
}
}
}
int main() {
freopen("biconex.in", "r", stdin);
freopen("biconex.out", "w", stdout);
citire();
solve();
afisare();
return 0;
}