Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //Основы теории графов и dfs. Теория. Задача G.
- #include <bits/stdc++.h>
- using namespace std;
- int n, m;
- vector < vector < int > > g;
- vector < int > color;
- vector < int > cur;
- int is = 0;
- void dfs(int v, int p) {
- if (color[v] == 1) {
- is = max(is, 1);
- return;
- }
- color[v] = 1;
- for (auto u : g[v]) {
- if (u != p) {
- dfs(u, v);
- }
- }
- color[v] = 2;
- }
- int main() {
- cin >> n >> m;
- g.resize(n);
- color.resize(n, 0);
- for (int i = 0; i < m; i++) {
- int a, b;
- cin >> a >> b;
- a--; b--;
- g[a].push_back(b);
- }
- for (int i = 0; i < n; i++) {
- if (color[i] == 0) {
- dfs(i, -1);
- }
- }
- cout << is;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement