Submission #37801257

Source Code Expand

#include <bits/stdc++.h>

#define x first
#define y second
#define IOS ios::sync_with_stdio(false)
#define cit cin.tie(0)
#define cot cout.tie(0)

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;

const int N = 110, M = 100010, MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const LL LLINF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-8;

int n, m;
int p[N];

int find(int x)
{
	if (p[x] != x) p[x] = find(p[x]);
	return p[x];
}

void solve();

int main()
{
	IOS;
	cit, cot;
	int T = 1;
//	cin >> T;
	while (T -- ) solve();
	return 0;
}

void solve()
{
	cin >> n >> m;
	for (int i = 1; i <= n; i ++ ) p[i] = i;
	while (m -- )
	{
		int u, v;
		cin >> u >> v;
		p[find(u)] = find(v);
	}
	
	int res = 0;
	for (int i = 1; i <= n; i ++ ) res += p[i] == i;
	cout << res << endl;
}

Submission Info

Submission Time
Task C - Count Connected Components
User hcywoi
Language C++ (GCC 9.2.1)
Score 300
Code Size 880 Byte
Status AC
Exec Time 8 ms
Memory 3636 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 300 / 300
Status
AC × 3
AC × 20
Set Name Test Cases
Sample 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt
All 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt, 01_random_00.txt, 01_random_01.txt, 01_random_02.txt, 01_random_03.txt, 01_random_04.txt, 01_random_05.txt, 01_random_06.txt, 01_random_07.txt, 01_random_08.txt, 01_random_09.txt, 02_corner_00.txt, 02_corner_01.txt, 02_corner_02.txt, 03_path_00.txt, 04_perfect_00.txt, 05_m_eq_0_00.txt, 06_n_eq_1_00.txt
Case Name Status Exec Time Memory
00_sample_00.txt AC 8 ms 3616 KiB
00_sample_01.txt AC 2 ms 3496 KiB
00_sample_02.txt AC 3 ms 3524 KiB
01_random_00.txt AC 2 ms 3520 KiB
01_random_01.txt AC 2 ms 3452 KiB
01_random_02.txt AC 2 ms 3512 KiB
01_random_03.txt AC 4 ms 3568 KiB
01_random_04.txt AC 3 ms 3568 KiB
01_random_05.txt AC 6 ms 3636 KiB
01_random_06.txt AC 4 ms 3584 KiB
01_random_07.txt AC 3 ms 3592 KiB
01_random_08.txt AC 2 ms 3592 KiB
01_random_09.txt AC 4 ms 3592 KiB
02_corner_00.txt AC 2 ms 3580 KiB
02_corner_01.txt AC 3 ms 3504 KiB
02_corner_02.txt AC 5 ms 3572 KiB
03_path_00.txt AC 3 ms 3460 KiB
04_perfect_00.txt AC 3 ms 3504 KiB
05_m_eq_0_00.txt AC 5 ms 3568 KiB
06_n_eq_1_00.txt AC 3 ms 3472 KiB