Submission #1160539
Source Code Expand
#include <vector> #include <list> #include <map> #include <set> #include <deque> #include <stack> #include <queue> #include <bitset> #include <algorithm> #include <functional> #include <numeric> #include <utility> #include <sstream> #include <iostream> #include <iomanip> #include <cstdio> #include <cmath> #include <cstdlib> #include <cctype> #include <string> #include <cstring> #include <ctime> using namespace std; typedef long long ll; typedef unsigned long long ull; static const double EPS = 1e-8; static const double PI = 4.0 * atan(1.0); static const double PI2 = 8.0 * atan(1.0); #define REP(i,n) for(int i=0;i<(int)n;++i) #define ALL(c) (c).begin(),(c).end() #define CLEAR(v) memset(v,0,sizeof(v)) #define MP(a,b) make_pair((a),(b)) #define ABS(a) ((a)>0?(a):-(a)) #define FOR(i,s,n) for(int i=s;i<(int)n;++i) int n, m; vector<int> es[100000]; int conn[100000]; void dfs(int v, int val) { if (conn[v] == val) return; conn[v] = val; REP(i, es[v].size()) dfs(es[v][i], val); } int main(int argc, char **argv) { cin >> n >> m; REP(i, m) { int a, b; cin >> a >> b; --a; --b; es[a].push_back(b); es[b].push_back(a); } memset(conn, -1, sizeof(conn)); int v = 0; REP(i, n) if (conn[i] < 0) dfs(i, v++); cout << (v - 1) << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | B - 道路工事 |
User | yupotown |
Language | C++14 (GCC 5.4.1) |
Score | 100 |
Code Size | 1345 Byte |
Status | AC |
Exec Time | 103 ms |
Memory | 7040 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 100 / 100 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | sample1.txt, sample2.txt |
All | 0.txt, 1.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 2.txt, 3.txt, 4.txt, 5.txt, 6.txt, 7.txt, 8.txt, 9.txt, sample1.txt, sample2.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
0.txt | AC | 3 ms | 2944 KB |
1.txt | AC | 3 ms | 2944 KB |
10.txt | AC | 3 ms | 2944 KB |
11.txt | AC | 3 ms | 2944 KB |
12.txt | AC | 3 ms | 2944 KB |
13.txt | AC | 3 ms | 2944 KB |
14.txt | AC | 3 ms | 2944 KB |
15.txt | AC | 56 ms | 4224 KB |
16.txt | AC | 3 ms | 2944 KB |
17.txt | AC | 3 ms | 2944 KB |
18.txt | AC | 3 ms | 2944 KB |
19.txt | AC | 103 ms | 7040 KB |
2.txt | AC | 3 ms | 2944 KB |
3.txt | AC | 3 ms | 2944 KB |
4.txt | AC | 3 ms | 2944 KB |
5.txt | AC | 3 ms | 2944 KB |
6.txt | AC | 3 ms | 2944 KB |
7.txt | AC | 3 ms | 2944 KB |
8.txt | AC | 3 ms | 2944 KB |
9.txt | AC | 3 ms | 2944 KB |
sample1.txt | AC | 3 ms | 2944 KB |
sample2.txt | AC | 3 ms | 2944 KB |