2227 邮票--FUoj(链接表+树的直径)

http://acm.fzu.edu.cn/problem.php?pid=2227

我感觉这道题可以随意搞

题目大意： 给你的一个图就是一条链，但是不知道起始点和结束点，而且每个点只会访问一次。

因为数太大了 只能用邻接表保存。

我不知不觉的用了树的直径   代码写的太乱了  但是是我自己写的，虽然这道题真的不难，但是还是很开心

#include<stdio.h>

#include<string.h>

#include<stdlib.h>

#include<math.h>

#include<algorithm>

#include<iostream>

#include<queue>

using namespace std;

#define N 201000

#define pi acos(-1.0)

#define ESP 1e-8

int head[N],ans,sum,vis[N],s1[N];

int x[N],y[N],a[N];

struct node

{

    int v,next;

}e[N];

void Add(int u,int v)

{

    e[ans].v=v;

    e[ans].next=head[u];

    head[u]=ans++;

}

int index=;

void solve(int s)

{

    index=s;

    s1[sum++]=a[s];

    for(int i=head[s];i!=-;i=e[i].next)

    {

        int v=e[i].v;

        if(!vis[v])

        {

            vis[v]=;

            solve(v);

        }

    }

}

int main()

{

    int n;

    while(scanf("%d",&n)!=EOF)

    {

        int cnt=;

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

        {

            scanf("%d %d",&x[i],&y[i]);

            a[cnt++]=x[i];

            a[cnt++]=y[i];

        }

        sort(a,a+cnt);

        int len=unique(a,a+cnt)-a;

        memset(head,-,sizeof(head));

        ans=;

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

        {

            int u=lower_bound(a,a+len,x[i])-a;

            int v=lower_bound(a,a+len,y[i])-a;

            Add(u,v);

            Add(v,u);

        }

        sum=;

        memset(vis,,sizeof(vis));

        vis[]=;

        solve();

        sum=;

        memset(vis,,sizeof(vis));

        vis[index]=;

        solve(index);

        if(s1[]>s1[sum-])

        {

            for(int i=sum-;i>=;i--)

                printf("%d%c",s1[i],(i==?'\n':' '));

        }

        else

            for(int i=;i<sum;i++)

                printf("%d%c",s1[i],(i==sum-?'\n':' '));

    }

    return ;

}