Solution UVA: 315 - Network

 

Problem	Verdict	Lang	Time	Best	Rank	Submit Time
| discuss315 - Network	Accepted	C++11	0.010	0.000	2767	29 secs ago

Suggest:

- To solve you need to know Finding Articulation Points (because this is a classic algogrithm of graph)

- I study Finding Articulation Points at link (vietnamese) you can try or look up on internet

#include<bits/stdc++.h>

using namespace std;

const int N= 1000111;

int n;

vector<int> a[N];

bool joint[N];

int timeDfs = 0, bridge = 0;

int low[N], num[N];

string s;

void dfs(int u, int pre) {

    int child = 0; // S? lu?ng con tr?c ti?p c?a d?nh u trong c�y DFS

    num[u] = low[u] = ++timeDfs;

    for (int v : a[u]) {

        if (v == pre) continue;

        if (!num[v]) {

            dfs(v, u);

            low[u] = min(low[u], low[v]);

            if (low[v] == num[v]) bridge++;

            child++;

            if (u == pre) { // N?u u l� d?nh g?c c?a c�y DFS

                if (child > 1) joint[u] = true;

            }

            else if (low[v] >= num[u]) joint[u] = true;

        }

        else low[u] = min(low[u], num[v]);

    }

}

int main(){

    ios::sync_with_stdio(false); cin.tie(nullptr);

   

    while(cin >> n && n){ getline(cin, s);

       

        for(int i=1; i<=n; i++) a[i].clear();

        for(int i=1; i<=n; i++) low[i]= 0;

        for(int i=1; i<=n; i++) num[i]= 0;

        for(int i=1; i<=n; i++) joint[i]= 0;

       

       

        timeDfs = 0, bridge = 0;

       

        while(getline(cin, s)){

            if (s[0]=='0') break;

           

            vector<int> vec;

            s+=' ';

            string x="";

           

            for(int i=0; s[i]; i++){

                if (s[i]==' '){

                    vec.push_back(stoi(x));

                    x="";

                }

                x+=s[i];

            }

           

            for(int i=1; i<vec.size(); i++) {

                a[vec[0]].push_back(vec[i]);

                a[vec[i]].push_back(vec[0]);

            }

        }

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

            if (!num[i]) dfs(i, i);

        int cntJoint = 0;

        for (int i = 1; i <= n; i++) cntJoint += joint[i];

   

        cout << cntJoint << '\n';

    }

}