Solution UVA: 247 - Calling Circles

 

Problem	Verdict	Lang	Time	Best	Rank	Submit Time
| discuss247 - Calling Circles	Accepted	C++11	0.060	0.000	3434	10 mins ago

Suggest:

- Order of ouput can diff

- This is basic problem for classic algorithm Finding Strongly Connected Components

- I feel Finding Strongly Connected Components so easy from link (vietnamese), you can try or look up from the internet (only need know to use template is easy to solve problem)

#include <bits/stdc++.h>

using namespace std;

const int maxN = 1000111;

int n, m;

int timeDfs = 0, scc = 0;

unordered_map<string, int> low, num;

unordered_map<string, bool> deleted;

unordered_map<string, bool> g, have;

stack <string> st;

vector<string> a;

stack <stack<string>> res;

void dfs(string u) {

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

    st.push(u);

    for (auto v : a)

    if (g[u+"+"+v]){

        if (deleted[v]) continue;

        if (!num[v]){

            dfs(v);

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

        }

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

    }

    if (low[u] == num[u]) {

        scc++;

        string v;

        stack<string> ans;

        do {

            v = st.top();

            st.pop();

            deleted[v] = true;

            ans.push(v);

        }

        while (v != u);

        res.push(ans);

    }

}

int main() {

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

   

    int cnt=0;

    while(cin >> n >> m){   if (n==0 && m==0) break;

   

        g.clear();

        low.clear();

        num.clear();

        deleted.clear();

        have.clear();

        a.clear();

   

               

        for (int i = 1; i <= m; i++) {

            string u, v;    cin >> u >> v;

            if (g[u+"+"+v]) continue;

            g[u+"+"+v]= true;

            if (not have[u]) a.push_back(u);

            if (not have[v]) a.push_back(v);

           

        }

        if (cnt!=0) cout<<"\n";

        cout<<"Calling circles for data set "<<++cnt<<":\n";

       

        for (auto i:a)

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

       

        while(!res.empty()){

       

            auto ans= res.top(); res.pop();

            while(!ans.empty()){

               

                cout<<ans.top(); ans.pop();

                if (ans.empty()) cout<<"\n"; else cout<<", ";      

            }

        }

    }

}