#include using namespace std; // Fast I/O #define FASTIO ios::sync_with_stdio(0); cin.tie(0); // Input/Output setups #ifndef ONLINE_JUDGE #define FILEIO freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #else #define FILEIO #endif // Debugging utilities #ifndef ONLINE_JUDGE #include "debug_template.c++" // Usages // 1. debug(var1, var2, var3, var4, ...); // - define void print() at global scope for user-defined structs/classes // 2. debugArr(arr, size); for array decay to pointer or int a[n] for C++17 #define CASEPRINT caseprint(); #else #define debug(...) #define debugArr(...) #define CASEPRINT #endif void caseprint(){ static int case_num = 1; cerr << '\n'; debug(case_num); case_num++; } // ------------------ Your code starts here ------------------ // Type aliases for convenience using ll = long long; using ul = unsigned long long; using ld = long double; // Global constants const ll MAX = 1e9; const ll MOD = 1e9 + 7; const int MAX_NODE = 100000; //@brief SCC (Strongly Connected Components) using Kosaraju's algorithm //https://www.acmicpc.net/source/94841693 //@tparam NodeType: type of node identifier (default is int) //@param n: number of nodes //@param graph: adjacency list (1-indexed (NodeType) //@param scc_component: output vector of vectors containing the SCC components (1-indexed (NodeType), empty vector) //@return scc_component: vector of vectors containing the SCC components (1-indexed (NodeType)) template void SCC(NodeType n, vector graph[], vector>& scc_component) { vector> rev_graph(n + 1); for(NodeType i = 1; i <= n; i++){ for(NodeType next : graph[i]) { rev_graph[next].push_back(i); } } // 1. Determine the finishing order of nodes using DFS vector visited(n + 1, false); stack s; function dfs1 = [&](NodeType node) { visited[node] = true; for(NodeType next : graph[node]) { if(!visited[next]) { dfs1(next); } } s.push(node); }; for(NodeType i = 1; i <= n; i++){ if(!visited[i]) { dfs1(i); } } // 2. Make the SCC component with the reverse graph fill(visited.begin(), visited.end(), false); scc_component.clear(); function&)> dfs2 = [&](NodeType node, vector& component) { visited[node] = true; component.push_back(node); for(NodeType next : rev_graph[node]) { if(!visited[next]) { dfs2(next, component); } } }; while(!s.empty()) { NodeType node = s.top(); s.pop(); if(!visited[node]) { vector component; dfs2(node, component); scc_component.push_back(component); } } return; } int main(){ ios::sync_with_stdio(0); cin.tie(0); int t; cin >> t; while(t--){ int n, m; cin >> n >> m; vector graph[MAX_NODE]; for(int i = 0; i < m; i++){ int a, b; cin >> a >> b; graph[a].push_back(b); graph[b].push_back(a); } vector> scc_components; SCC(n, graph, scc_components); cout << scc_components.size() << '\n'; } return 0; }

제출 #113193

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: