14956. Submerging Islands

Vice City is built over a group of islands, with bridges connecting them. As anyone in Vice City knows, the biggest fear of vice-citiers is that some day the islands will submerge. The big problem with this is that once the islands submerge, some of the other islands could get disconnected. You have been hired by the mayor of Vice city to tell him how many islands, when submerged, will disconnect parts of Vice City. You should know that initially all the islands of the city are connected.

Input. Consist of a series of test cases. Each test case will start with the number n (1 ≤ n ≤ 10⁴) of islands, and the number m of bridges (1 ≤ m ≤ 10⁵). Following there will be m lines each describing a bridge. Each of these m lines will contain two integers u_i, v_i (1 ≤ u_i, v_i ≤ n), indicating that there is a bridge connecting islands u_i and v_i. The input ends with a case where n = m = 0.

Output. For each case on the input you must print a line indicating the number of islands that, when submerged, will disconnect parts of the city.

Sample Input	Sample Output
3 3 1 2 2 3 1 3 6 8 1 3 6 1 6 3 4 1 6 4 5 2 3 2 3 5 0 0	0 1

РЕШЕНИЕ

графы – точки сочленения

Анализ алгоритма

В заданном графе следует найти количество точек сочленения.

Реализация алгоритма

#include <cstdio>

#include <vector>

#include <set>

#include <cstring>

#define MAX 10010

using namespace std;

vector<int> graph[MAX];

int used[MAX], d[MAX], up[MAX];

int i, n, m, a, b, time;

set<int> ArtPoints;

set<int>::iterator iter;

void dfs (int v, int p = -1)

{

int i, to, children;

used[v] = 1;

d[v] = up[v] = time++;

children = 0;

for (i = 0; i < graph[v].size(); i++)

{

to = graph[v][i];

if (to == p) continue;

if (used[to])

up[v] = min (up[v], d[to]);

else

{

dfs (to, v);

up[v] = min (up[v], up[to]);

if ((up[to] >= d[v]) && (p != -1)) ArtPoints.insert(v);

children++;

}

}

if ((p == -1) && (children > 1)) ArtPoints.insert(v);

}

int main(void)

{

while(scanf("%d %d",&n,&m), n + m)

{

for(i = 0; i <= n; i++) graph[i].clear();

memset(used,0,sizeof(used));

memset(d,0,sizeof(d));

memset(up,0,sizeof(up));

ArtPoints.clear();

for(i = 0; i < m; i++)

{

scanf("%d %d",&a,&b);

graph[a].push_back(b); graph[b].push_back(a);

}

time = 1;

for(i = 1; i <= n; i++)

if (!used[i]) dfs(i);

printf("%d\n",ArtPoints.size());

}

return 0;

}