낡은 다리 문제 풀이

제목:
지금 은 N N 개 섬 과 M 좌 교가 있 습 니 다.
제 i i 개 다 리 는 A. A. Ai 와 B. B. Bi 개의 섬 이 양 방향 으로 연결 되 어 있다.
처음에 우 리 는 그 중의 일부 다 리 를 이용 하여 어느 두 섬 사 이 를 여행 할 수 있 었 다.
그러나 이 다리 들 은 모두 낡 아 무 너 질 것 으로 조 사 됐 으 며, 무 너 지 는 순 서 는 첫 번 째 다리 부터 M 번 째 다리 까지 인 것 으로 나 타 났 다.
남 은 다 리 는 a a a 개 섬 과 b b 개 섬 이 서로 도착 하지 못 해 섬 이 불편 하 다.
하나 하나 에 대해 서 는 i (1 < = i < = M) (1 < = i < = M) (1 < = i < = M) 다리 가 무 너 진 후 이렇게 불편 한 섬 을 찾 는 것 이 (a, b) (a, b) (a, b) (a, b) (a, b) (a < b) 에 얼마나 됩 니까?
입력 형식:
첫 줄 에는 두 개의 정수 와 섬 을 나타 내 는 N N N 수량 과 다리 의 M M M 수량 이 있다.
이 어 엠 엠 엠 엠 엠 엠 엠 엠 엠 엠 엠 엠 엠 엠 엠 엠 엠 엠 엠 엠 엠 엠 엠 엠 엠 엠 엠 엠 엠 엠 엠 엠 엠 엠 엠 엠 엠 엠 엠 엠 엠 엠 엠 엠 엠 엠 엠 엠 엠 엠 엠 엠 엠 엠 엠 엠 엠 엠 엠 엠 엠 엠 엠 엠 엠 엠 엠 엠 엠 엠 엠 엠 엠 엠 엠 엠 엠 엠 엠 엠 엠 엠 엠 엠 엠 엠 엠 엠 엠
출력 형식:
출력 은 M M M 줄 이 있 습 니 다. 줄 마다 정 수 를 출력 합 니 다. 첫 번 째 다리 가 무 너 진 후에 도착 하기 어 려 운 섬 대 (a, b) (a, b) (a, b) (a, b) (a, b) 의 수량 을 표시 합 니 다. 결 과 는 32 32 32 비트 의 i n t int 크기 를 초과 할 수 있 습 니 다.
입력:
입력 샘플 1:
4 5 1 2 3 4 1 3 2 3 1 4
입력 샘플 2:
6 5 2 3 1 2 5 6 3 4 4 5
출력:
출력 예시 1:
0 0 4 5 6
출력 예시 2:
8 9 12 14 15
문제 풀이:
먼저 다 리 를 파괴 하 는 방법 이 비교적 어렵 습 니 다. 우 리 는 1 - m 에서 차례대로 다 리 를 파괴 할 수 있 습 니 다. m - 1 에서 차례대로 다 리 를 건설 하고 하나의 배열 tot [i] 로 i 번 째 다리 의 연결 수 를 저장 할 수 있 습 니 다. tot [m + 1] 를 n * (n - 1) / 2 로 초기 화 할 수 있 습 니 다. 즉, 그 어떠한 다리 도 건설 하지 않 고 점 과 점 의 연결 수 입 니 다.그럼 tot [i] 어떻게 옮 겨 야 되 지?tot [i + 1] 은 i + 1 개의 다 리 를 건설 하 는 연결 수 를 나타 내기 때문에 tot [i] = tot [i + 1] - i 번 다 리 를 건설 하 는 데 새로 추 가 된 연결 수 입 니 다.
부분 코드:

 tot[m + 1] = n * (n - 1) / 2;//   
    for (int i = m; i >= 2; i--) {// m          
    	int e = FindSet(c[i].a), f = FindSet(c[i].b);
    	if(e != f){//     i          
			UnionSet(c[i].a, c[i].b);
    		int q = sum[e] * sum[f];//sum[i]    i       
    		//q        
       		tot[i] = tot[i + 1] - q;//tot[i] = tot[i + 1] -   i        。
        	sum[FindSet(c[i].a)] = sum[e] + sum[f];//      i  ，e f       ， e，f             
		}
        else{//         i+1      
        	tot[i] = tot[i + 1];
		}
    }

코드:

#include 
#include 
using namespace std;
long long fa[300005], rank[300005];
long long tot[300005], sum[300005];
struct node {
   long long a, b;
} c[300005];
void MakeSet(int n) {
    for (int i = 1; i <= n; i++) {
        fa[i] = i;
        rank[i] = 0;
        sum[i] = 1;
    }
}
int FindSet(int x) {
    if (fa[x] != x) {
        fa[x] = FindSet(fa[x]);
    }
    return fa[x];
}
void UnionSet(int w, int e) {
    int u = FindSet(w), v = FindSet(e);
    if (u == v) {
        return;
    }
    if (rank[u] > rank[v]) {
        fa[v] = u;
    } else {
        fa[u] = v;
        if (rank[u] == rank[v]) {
            rank[u]++;
        }
    }
}
int main() {
    long long n, m, q, x, y;
    scanf("%lld %lld", &n, &m);
    MakeSet(n);
    for (int i = 1; i <= m; i++) {
        scanf("%lld %lld", &c[i].a, &c[i].b);
    }
    tot[m + 1] = n * (n - 1) / 2;
    for (int i = m; i >= 2; i--) {
    	int e = FindSet(c[i].a), f = FindSet(c[i].b);
    	if(e != f){
			UnionSet(c[i].a, c[i].b);
    		int q = sum[e] * sum[f];
       		tot[i] = tot[i + 1] - q;
        	sum[FindSet(c[i].a)] = sum[e] + sum[f];
		}
        else{
        	tot[i] = tot[i + 1];
		}
    }
    for (int i = 2; i <= m + 1; i++) {
        printf("%lld
", tot[i]);
    }
    return 0;
}