1013 Battle Over Cities (25point (s)) 는 빅 데이터 샘플 에서 scanf 를 사용 하 는 문제 에 주의 하고 수집 해 야 합 니 다.

1934 단어
기본 사상:
어렵 지 는 않 지만 집합 을 이용 하여 조회 하 였 으 나 마지막 테스트 점 에 걸 려 TL 의 문제 가 존재 하 였 으 며, 마지막 으로 cin 과 scanf 효율 의 문제 임 을 발견 하 였 다.
 
관건:
이후 입 출력 은 OJ 방면 에서 scanf 를 사용 합 니 다.
char a [] string 돌리 기 직접 cstr () 와 s = a 면 됩 니 다.
  
#include
#include
#include
#include 
#include
#include
#include
#include
#include
#include
using namespace std;

const int maxn = 1010;
vector>matrix;
vectorfather;
vectorflag;

int findfather(int n) {
	int temp = n;
	while (n != father[n]) {
		n = father[n];
	}
	while(temp!=father[temp]){
		int z = temp;
		temp = father[temp];
		father[z] = n;
	}
	return n;
}

void union_father(int a, int b) {
	int aa = findfather(a);
	int bb = findfather(b);
	if (aa != bb) {
		father[aa] = bb;
	}
}

void init(int n) {
	father.resize(n + 1);
	flag.resize(n + 1);
	fill(flag.begin(),flag.end(), true);
	for (int i = 0; i < father.size(); i++) {
		father[i] = i;
	}
}

int cnt(int n) {
	int c=0;
	for (int i = 1; i <= n; i++) {
		if (father[i] == i) {
			c++;
		}
	}
	return c-1;
}



int main() {
	//fill(matrix, matrix + maxn * maxn, 0);
	int n, m, k;
	int a, b;
	scanf("%d %d %d", &n, &m, &k);
	matrix.resize(n + 1);
	for (int i = 0; i < m; i++) {
		scanf("%d %d", &a, &b);
		matrix[a].push_back(b);
		matrix[b].push_back(a);
	}
	for (int i = 0; i < k; i++) {
		cin >> a;
		init(n);
		flag[a] = false;
		//      ；
		for (int i = 1; i <= n; i++) {
			for (int j = 0; j < matrix[i].size(); j++) {
				if (flag[i] && flag[matrix[i][j]]) {
					//       ；
					union_father(i, matrix[i][j]);
				}
			}
		}
		printf("%d
", cnt(n) - 1);
		//flag[a] = true;
	}
	return 0;
}

Flume - 1.7.0 의 설치 와 설정
RequestAnimationFrame 자동 반복()

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage