Algorithm/Topcoder_RoadReconstruction.cpp at master · nikhilkarnwal/Algorithm · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cctype>

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>
#include <sstream>
#include <set>
#include <map>

using namespace std;

class RoadReconstruction
    {
    public:
    int p[50];
    int findset(int a){
        if(p[a]==a)
            return a;
        p[a]=findset(p[a]);
        return p[a];
    }
    void merge(int a,int b){
            int _hd_a=findset(a);
            int _hd_b=findset(b);
            if(_hd_a==_hd_b)
                return ;
            else if(_hd_a<_hd_b)
                {
                p[_hd_b]=_hd_a;
                }
            else
                p[_hd_a]=_hd_b;
        }
    vector<string> split(string str, char delimiter) {
          vector<string> internal;
          stringstream ss(str); // Turn the string into a stream.
          string tok;

          while(getline(ss, tok, delimiter)) {
            internal.push_back(tok);
          }
          return internal;
	}
    string selectReconstruction(vector<string> rd){
        for(int i=0;i<50;i++)
            p[i]=i;
        map<int,map<string,vector<int> > > roads;
        map<string,int> city;
        int cnt=0;
        for(int i=0;i<rd.size();i++){
            vector<string> cols=split(rd[i],' ');
            int c1,c2;
            if(city.count(cols[1])>0)
                c1=city[cols[1]];
            else
                cout<<(c1=(city[cols[1]]=cnt++))<<" ";
            if(city.count(cols[2])>0)
                c2=city[cols[2]];
            else
                cout<<(c2=(city[cols[2]]=cnt++))<<" ";
            if(cols.size()==3)
                merge(c1,c2);
            else{
                map<string,vector<int> > temp;
                vector<int> _temp(2);
                _temp[0]=c1;
                _temp[1]=c2;
                temp[cols[0]]=_temp;
                if(roads.count(stoi(cols[3]))>0)
                    roads[stoi(cols[3])][cols[0]]=_temp;
                else
                    roads[stoi(cols[3])]=temp;
            }
         }
            map<int,map<string,vector<int> > >::iterator it;
            string ret="";
        vector<string> _ret;
            for(it=roads.begin();it!=roads.end();it++){
                map<string,vector<int> > temp=it->second;
                map<string,vector<int> >::iterator it_temp;
                for(it_temp=temp.begin();it_temp!=temp.end();it_temp++){
                    string id=it_temp->first;
                    vector<int> vec=it_temp->second;
                    if(findset(vec[0])==findset(vec[1]))
                        continue;
                    merge(vec[0],vec[1]);
                    _ret.push_back(id);

                }
            }
            for(int i=0;i<cnt;i++)
                if(p[i]!=0)
                findset(i);
            for(int i=0;i<cnt;i++)
                if(p[i]!=0)
                return "IMPOSSIBLE";
            sort(_ret.begin(),_ret.end());
            for(int i=0;i<_ret.size();i++)
                if(ret=="")
                    	ret+=_ret[i];
                    else
                        ret+=" "+_ret[i];
            return ret;
    }
    };