Submission #1356297
Source Code Expand
#include "bits/stdc++.h"
#include <regex>
#define _USE_MATH_DEFINES
#include <math.h>
using namespace std;
#ifndef _DEBUG
#define main_ main
#endif
#define FOR(i,s,e) for (int i = int(s); i < int(e); ++i)
#define REP(i,e) FOR(i,0,e)
#define INF (INT_MAX/2)
#define EPS (1.0e-8)
#define LINF (LONG_MAX/2)
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<bool> vb;
typedef vector<string> vs;
template <typename T>
using keyVal = pair<string, T>;
template<typename T>
bool val_greater(const keyVal<T>& left, const keyVal<T>& right) {
return left.second > right.second;
}
vs split(string str, char sep) {
vs v; stringstream ss(str); string t;
while (getline(ss, t, sep)) v.push_back(t);
return v;
}
class UF {
vi p;
public:
UF(int N) {
p.resize(N);
FOR(i, 0, N) p[i] = i;
}
void unite(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX == rootY) return;
p[rootX] = rootY;
}
int find(int x){
if (x == p[x]) return x;
p[x] = find(p[x]);
return p[x];
}
bool same(int x, int y){
return find(x) == find(y);
}
};
int main_() {
cin.tie(0);
ios::sync_with_stdio(false);
int N, M; cin >> N >> M;
UF uf(N);
FOR(i, 0, M) {
int a, b;
cin >> a >> b;
a--; b--;
uf.unite(a, b);
}
int cnt = 0;
vb used(N, false);
FOR(i, 0, N) {
int p = uf.find(i);
if (used[p]) continue;
used[p] = true;
cnt++;
}
int ans = cnt - 1;
cout << ans << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
B - 道路工事 |
User |
apprec |
Language |
C++14 (GCC 5.4.1) |
Score |
100 |
Code Size |
1693 Byte |
Status |
AC |
Exec Time |
22 ms |
Memory |
640 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 |
1 ms |
256 KB |
1.txt |
AC |
1 ms |
256 KB |
10.txt |
AC |
1 ms |
256 KB |
11.txt |
AC |
1 ms |
256 KB |
12.txt |
AC |
1 ms |
256 KB |
13.txt |
AC |
1 ms |
256 KB |
14.txt |
AC |
1 ms |
256 KB |
15.txt |
AC |
14 ms |
256 KB |
16.txt |
AC |
2 ms |
640 KB |
17.txt |
AC |
2 ms |
640 KB |
18.txt |
AC |
2 ms |
640 KB |
19.txt |
AC |
22 ms |
640 KB |
2.txt |
AC |
1 ms |
256 KB |
3.txt |
AC |
1 ms |
256 KB |
4.txt |
AC |
1 ms |
256 KB |
5.txt |
AC |
1 ms |
256 KB |
6.txt |
AC |
1 ms |
256 KB |
7.txt |
AC |
1 ms |
256 KB |
8.txt |
AC |
1 ms |
256 KB |
9.txt |
AC |
1 ms |
256 KB |
sample1.txt |
AC |
1 ms |
256 KB |
sample2.txt |
AC |
1 ms |
256 KB |