ASA23/proj2.cpp at main · WhiteSoxx/ASA23 · 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
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include <iostream>
#include <list>
#include <vector>
#include <stack>
#include <cstring>
#include <chrono>

#define WHITE 0
#define GRAY 1
#define BLACK 2
using namespace std;
//using namespace chrono;
int _V,_E,_SCC = 0;
int _time = 0,_end = 0;
int _path = 0;
struct Vertice{
    int color = WHITE;
    int end_time = 0;
    int scc = 0;
};
vector<Vertice> _vertices;
vector<int> _second_order;
vector<int> _scc_max_path;
vector<vector<int>> graph;
vector<vector<int>> graphT;

int main(){
    //auto start_time = high_resolution_clock::now();
    int u,v;
    if(scanf("%d %d",&_V,&_E))
    if (_V < 2){
        printf("%d\n",0);
        return 0;
    }
    _end = _V;
    graph =  vector<vector<int>>(_V+1,vector<int>());
    graphT = vector<vector<int>>(_V+1,vector<int>());
    _vertices = vector<Vertice> (_V+1);
    _second_order = vector<int>(_V+1);
    _scc_max_path = vector<int>(_V+1);
    //memset(_scc_max_path, 0, sizeof(*_scc_max_path));
    //_scc_max_path = {0};
    for (int i = 1; i <= _E; i++){
        if (i <= _V) _scc_max_path[i] = 0;
        if(scanf("%d %d",&u,&v))
        graph[u].push_back(v);
        graphT[v].push_back(u);
    }
    stack<int> stack;
    for (int i = 1; i <= _V; i++) {
        if (!_vertices[i].color){ // WHITE
        //if GRAY it's in the stack already
            stack.push(i);
            while(!stack.empty()) {
                int V = stack.top();

                int color = _vertices[V].color;
                switch(color) {
                    case(WHITE): {
                        _time++;
                        _vertices[V].color = GRAY;
                        for(int neighbour : graph[V]){
                            if(_vertices[neighbour].color == WHITE)
                                stack.push(neighbour);
                        }
                        break;
                    }
                    case(GRAY): {
                            _vertices[V].color = BLACK;
                            _time++;
                            _vertices[V].end_time = ++_time;
                            _second_order[_end] = V;
                            _end--;
                        }
                    default: stack.pop();

                }
            }
        }
    }

    // delete[] graph;
    // delete[] _vertices;
    _vertices = vector<Vertice> (_V+1);

    for (int i = 1; i <= _V; i++) {
        if (!_vertices[_second_order[i]].color){ // WHITE
        //if GRAY it's in the stack already
            stack.push(_second_order[i]);
            _SCC++;
            while(!stack.empty()) {
                int V = stack.top();

                int color = _vertices[V].color;
                switch(color) {
                    case(WHITE): {
                        _vertices[V].color = GRAY;
                        _vertices[V].scc = _SCC;
                        for(int neighbour : graphT[V]){
                            if(_vertices[neighbour].color == WHITE)
                                stack.push(neighbour);
                            if (_vertices[neighbour].color == BLACK && (_vertices[neighbour].scc != _SCC)){
                                _scc_max_path[_SCC] = max(_scc_max_path[_SCC], _scc_max_path[_vertices[neighbour].scc] + 1);
                                _path = max(_scc_max_path[_SCC],_path);
                            }
                        }
                        break;
                    }
                    case(GRAY): {
                        _vertices[V].color = BLACK;
                    }
                    default: stack.pop();
                }
            }
        }
    }
    // delete[] graphT;


    // delete[] _scc_max_path;
    // delete[] _second_order;
    // delete[] _vertices;

    printf("%d\n",_path);
    // auto end_time = high_resolution_clock::now();
    // auto duration = duration_cast<milliseconds>(end_time - start_time);
    // cout << "it took " << duration.count()<<endl;
    return 0;
}