fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. // Stałe dla maksymalnych rozmiarów, zgodnie z treścią zadania (1 mln)
  8. const int MAXN = 1000005;
  9. const int MAXM = 1000005;
  10.  
  11. // Struktura do przechowywania oryginalnych krawędzi, aby ustalić kierunek
  12. struct Edge {
  13.     int u, v;
  14. } edges[MAXM];
  15.  
  16. // Lista sąsiedztwa: pair<sąsiad, numer_krawędzi>
  17. vector<pair<int, int>> adj[MAXN];
  18.  
  19. // Tablice pomocnicze do DFS i znajdowania mostów
  20. int tin[MAXN];      // Time In - czas wejścia do wierzchołka
  21. int low[MAXN];      // Low Link - najniższy tin osiągalny przez krawędź powrotną
  22. int timer;          // Licznik czasu
  23. bool visited[MAXN]; // Czy odwiedzono
  24.  
  25. // Tablica na wynikowe znaki kierunków (>, <)
  26. char result_dirs[MAXM];
  27.  
  28. int bridges_count = 0; // Licznik mostów
  29.  
  30. // Główna funkcja DFS
  31. void dfs(int u, int p_edge_id) {
  32.     visited[u] = true;
  33.     tin[u] = low[u] = ++timer;
  34.  
  35.     for (auto& edge : adj[u]) {
  36.         int v = edge.first;
  37.         int id = edge.second;
  38.  
  39.         // Nie wracamy tą samą krawędzią, którą przyszliśmy (ale równoległą możemy!)
  40.         if (id == p_edge_id) continue;
  41.  
  42.         if (visited[v]) {
  43.             // Krawędź powrotna lub już odwiedzona inna krawędź równoległa
  44.             low[u] = min(low[u], tin[v]);
  45.  
  46.             // Jeśli kierunek tej krawędzi nie został jeszcze ustalony, ustalamy go teraz.
  47.             // Dla krawędzi powrotnej orientujemy u -> v (domykamy cykl)
  48.             if (result_dirs[id] == 0) {
  49.                 if (edges[id].u == u) result_dirs[id] = '>'; // u to pierwszy wierzchołek z wejścia
  50.                 else result_dirs[id] = '<';                  // u to drugi wierzchołek z wejścia
  51.             }
  52.         } else {
  53.             // Krawędź drzewowa
  54.             // Orientujemy zgodnie z kierunkiem DFS: u -> v
  55.             if (edges[id].u == u) result_dirs[id] = '>';
  56.             else result_dirs[id] = '<';
  57.  
  58.             dfs(v, id);
  59.  
  60.             low[u] = min(low[u], low[v]);
  61.  
  62.             // Sprawdzenie warunku na most
  63.             if (low[v] > tin[u]) {
  64.                 bridges_count++;
  65.             }
  66.         }
  67.     }
  68. }
  69.  
  70. int main() {
  71.     // Optymalizacja I/O
  72.     ios_base::sync_with_stdio(false);
  73.     cin.tie(NULL);
  74.  
  75.     int n, m;
  76.     if (!(cin >> n >> m)) return 0;
  77.  
  78.     for (int i = 1; i <= m; ++i) {
  79.         cin >> edges[i].u >> edges[i].v;
  80.         // Dodajemy krawędź do listy sąsiedztwa obu wierzchołków
  81.         adj[edges[i].u].push_back({edges[i].v, i});
  82.         adj[edges[i].v].push_back({edges[i].u, i});
  83.         result_dirs[i] = 0; // 0 oznacza, że kierunek nie został jeszcze nadany
  84.     }
  85.  
  86.     int connected_components = 0;
  87.  
  88.     // Uruchamiamy DFS dla każdej spójnej składowej grafu
  89.     for (int i = 1; i <= n; ++i) {
  90.         if (!visited[i]) {
  91.             connected_components++;
  92.             dfs(i, -1);
  93.         }
  94.     }
  95.  
  96.     // Minimalna liczba osiedli = liczba spójnych składowych + liczba mostów
  97.     cout << connected_components + bridges_count << "\n";
  98.  
  99.     // Wypisujemy ciąg znaków reprezentujący kierunki
  100.     for (int i = 1; i <= m; ++i) {
  101.         // Zabezpieczenie: jeśli z jakiegoś powodu (np. graf niespójny i pętle) 
  102.         // kierunek nie został ustawiony, domyślnie dajemy '>'
  103.         if (result_dirs[i] == 0) cout << '>'; 
  104.         else cout << result_dirs[i];
  105.     }
  106.     cout << "\n";
  107.  
  108.     return 0;
  109. }
Success #stdin #stdout 0.01s 30192KB
comments (?)
stdin
copy 
7 7
1 2
1 3
2 3
3 4
4 5
4 5
7 6
stdout
copy 
4
><>>><<
https://ideone.com/CeFKtQ
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!