A simple Blog for wyx I've been down the bottle hoping.
1098: [POI2007]办公楼biu 宽搜 链表 图论
发表于: | 分类: Oi | 评论:0 | 阅读:163

早上在火车站写的……

题还是挺简单的,首先就是两个人不在一起必须互相知道电话号,那么互相不知道电话号的必然需要在一起,所以其实就是求原图的一个反图,他的所有极大联通块的大小

直建出反图不是$Tle+Mle$?

废话,当然$Tle+Mle$

但是直接搜不就行了

我们需要维护一个数据结构支持插入删除,并保持有序

链表即可,复杂度均摊$O(n)$

#include <vector>
#include <queue>
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
const int N = 1e5+10;
using namespace std;
vector <int> g[N];

inline int read() {
    int x=0,f=1;char ch = getchar();
    while(ch < '0' || ch > '9') {if(ch == '-')f=-1;ch = getchar();}
    while(ch >='0' && ch <='9') {x=(x<<1)+(x<<3)+ch-'0';ch = getchar();}
    return x*f;
}

int n,m,cnt;
bool vis[N];
int next[N],pre[N];
int num[N];

void erase(int x) {
    next[pre[x]] = next[x];
    pre[next[x]] = pre[x] ;
}

void solve(int x) {
    queue <int> q;
    q.push(x);
    vector <int> :: iterator it;
    while(!q.empty()) {
        int tt = q.front(); q.pop();
        for(it = g[tt].begin(); it != g[tt].end(); it ++) vis[*it] = 1;
        for(int i=next[0]; i<=n; i = next[i]) {
            if(!vis[i]) {
                erase(i);
                num[cnt] ++;
                q.push(i);
            }
        }
        for(it = g[tt].begin(); it != g[tt].end(); it ++) vis[*it] = 0;
    }
}

int main() {
    n = read(), m = read();
    for(int i=0;i<=n;++i) next[i] = i + 1 , pre[i+1] = i;
    for(int i=1;i<=m;++i) {
        int x = read(), y = read();
        g[x].push_back(y), g[y].push_back(x);
    }
    for(int i=next[0]; i<= n; i = next[0]) {
        erase(i);
        num[++cnt] = 1;
        solve(i);
    }
    cout << cnt << endl;
    sort(num+1,num+cnt+1);
    for(int i=1;i<=cnt;++i) printf("%d ",num[i]);
}

Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP