• API
• FAQ
• Tools
• Archive
SHARE
TWEET # Untitled a guest Dec 14th, 2019 80 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <vector>
2. #include <iostream>
3. #include <queue>
4. #include <math.h>
5.
6. class MatrixGraph {
7.
8. public:
9.
10.     std::vector<std::vector<int>> data;
11.
12.     MatrixGraph(int N);
13.
14.     ~MatrixGraph() {};
15.
16.     void AddEdge(int from, int to);
17.
18. };
19.
20.
21. MatrixGraph::MatrixGraph(int N) {
22.     std::vector<bool> tmp;
23.     for (int i = 0; i < N; i++) {
24.         std::vector<int> tmp;
25.         data.push_back(tmp);
26.     }
27.
28. }
29.
30.
31. void MatrixGraph::AddEdge(int from, int to) {
32.     data.at(from).push_back(to);
33.     data.at(to).push_back(from);
34. }
35.
36.
37. int main()
38. {
39.     int N, M;
40.     std::cin >> N >> M;
41.     int res = 0;
42.     MatrixGraph graph(N);
43.
44.     for (int i = 0; i < M; i++) {
45.         int from, to;
46.         std::cin >> from >> to;
48.     }
49.     int sum = 0;
50.     for (int j = 0; j < N; j++) {
51.         std::queue<int> q;
52.         q.push(j);
53.         std::vector<bool> used(N);
54.         std::vector<int> p(N);
55.         used[j] = true;
56.         sum++;
57.         p[j] = -1;
58.         while (!q.empty()) {
59.             int v = q.front();
60.             q.pop();
61.             for (int i = 0; i < graph.data[v].size(); i++) {
62.                 int to = graph.data[v][i];
63.                 if (!used[to]) {
64.                     used[to] = true;
65.                     q.push(to);
66.                     p[to] = v;
67.                     sum++;
68.                 }
69.                 else {
70.                     if (to != p[v]) {
71.                         res++;
72.                     }
73.                 }
74.             }
75.         }
76.     }
77.     std::cout << res;
78.     system("pause");
79.     return 0;
80. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.

Top