My_Profile-/Cycle_Finding.cpp at master · raihan02/My_Profile- · 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
int dis[10002];
vi node[10002];

#define explored -2
#define visited -3

bool ans=true;

void cycleFinding(int u){
    dis[u]=explored;
    f(j,0,node[u].size()){
        int v=node[u][j];
        if(v==u){
            ans=false;
            return;
        }
        if(dis[v]==unvisited){
            dis[v]=u;
            cycleFinding(v);
        }
        else if(dis[v]==explored){
            ans=false;
            return;
        }
    }
    dis[u]=visited;
}

int main(){
   // fin(prob);
    ft{
        ans=true;
        mem(dis, unvisited);
        int assi=0;
        map<st, int>mymap;
        c(int, n);
        f(i,0,n){
             c(st, frst);c(st, scnd);
            if(mymap.find(frst)==mymap.end()) mymap[frst]=assi++;
            if(mymap.find(scnd)==mymap.end()) mymap[scnd]=assi++;
            int a=mymap[frst];
            int b=mymap[scnd];
            node[a].pb(b);
        }
        f(i,0,assi){
            if(dis[i]==unvisited) cycleFinding(i);
            node[i].clear();
        }
        if(ans) cases<<"Yes"<<endl;
        else cases<<"No"<<endl;
    }
return 0;
}