[CodeForces]String Reconstruction

http://codeforces.com/contest/828/problem/C

并查集的神奇应用。

#include<bits/stdc++.h>

using namespace std;

const int maxn=10000005;

char s[maxn];

string ss[100000];

vector<int> g[100000];

int fa[maxn];

int findfa(int x)

{

    if (fa[x]==x) return x;

    else return fa[x]=findfa(fa[x]);

}

void merge(int u,int v)

{

    int f1=findfa(u);

    int f2=findfa(v);

    if (f1!=f2)

    {

        fa[f1]=f2;

    }

}

int main()

{

    int n;

    scanf("%d",&n);

    int ma=0;

    for (int i=0;i<n;i++)

    {

        cin >>ss[i];

        int k;

        scanf("%d",&k);

        int l=ss[i].length();

        for (int j=0;j<k;j++)

        {

            int x;

            scanf("%d",&x);

            g[i].push_back(x);

            if (x+l-1>ma) ma=x+l-1;

        }

    }

    s[ma+1]=0;

    for (int i=0;i<=ma+1;i++) fa[i]=i;

    for (int i=0;i<n;i++)

    {

        for (int j=0;j<g[i].size();j++)

        {

            int p=g[i][j];

            for (int k=findfa(p);k<=p+ss[i].length()-1;k=findfa(k+1))

            {

                s[k]=ss[i][k-p];

                merge(k,p+ss[i].length());

            }

        }

    }

    for (int i=1;i<=ma;i++)

        if (s[i]==0) s[i]='a';

    printf("%s",s+1);

    return 0;

}