toj 144

domen111

為什麼第一筆測資就是會WA啊?

[C++] 純文本查看 復制代碼

#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
vector<int> g[100010];
int dis[100010];
int dfs(int s)
{
    memset(dis,-1,sizeof dis);
    vector<int> stk;
    stk.push_back(s);
    dis[s]=0;
    int farthest=s;
    while(!stk.empty())
    {
        int now=stk.back();
        stk.pop_back();
        for(int i=0;i<g[now].size();i++)
            if(dis[g[now][i]]==-1)
            {
                dis[g[now][i]]=dis[now]+1;
                stk.push_back(g[now][i]);
                if(dis[g[now][i]]>dis[farthest])
                    farthest=g[now][i];
            }
    }
    return farthest;
}
int main()
{
    ios::sync_with_stdio(0);
    int n,m;
    while(cin>>n>>m)
    {
        for(int i=0;i<n;i++)
            g[i].clear();
        for(int i=0;i<m;i++)
        {
            int a,b;
            cin>>a>>b;
            g[a].push_back(b);
            g[b].push_back(a);
}
        int a=dfs(0);
        int b=dfs(a);
        cout<<dis[b]<<endl;
    }
}

Sylveon

只有一筆測資，多讀會讀到怪怪的東西歐

xiplus

那如果第一筆RE勒==

[C++] 純文本查看 復制代碼

#include <cstdio> //c¿é¤J¿é¥X
#include <iostream>
using namespace std;
struct V{
    int a;
    int b;
    bool x;
};
V v1[100001],v2[100001];
int main(){
	int n,m;
    while(~scanf("%d",&n)){
    	scanf("%d",&m);
    	for(int q=0;q<m;q++){
            scanf("%d%d",&v1[q].a,&v1[q].b);
            v1[q].x=0;
            v2[q].a=v1[q].a;
            v2[q].b=v1[q].b;
            v2[q].x=0;
        }
        int tree[n];
        for(int q=0;q<n;q++)tree[q]=-1;
        tree[v1[0].a]=0;
	    tree[v1[0].b]=1;
	    v1[0].x=1;
	    bool empty=1;
        while(empty){
            empty=0;
            for(int q=0;q<m;q++){
                if(v1[q].x==0&&tree[v1[q].a]!=-1){
                    tree[v1[q].b]=tree[v1[q].a]+1;
                    v1[q].x=1;
                    empty=1;
                }
                else if(v1[q].x==0&&tree[v1[q].b]!=-1){
                    tree[v1[q].a]=tree[v1[q].b]+1;
                    v1[q].x=1;
                    empty=1;
                }
            }
        }
        int maxd=-1,maxn=-1;
        for(int q=0;q<n;q++){
            if(tree[q]>maxd){
                maxd=tree[q];
                maxn=q;
            }
            tree[q]=-1;
        }
        tree[maxn]=0;
        empty=1;
        while(empty){
            empty=0;
            for(int q=0;q<m;q++){
                if(v2[q].x==0&&tree[v2[q].a]!=-1){
                    tree[v2[q].b]=tree[v2[q].a]+1;
                    v2[q].x=1;
                    empty=1;
                }
                else if(v2[q].x==0&&tree[v2[q].b]!=-1){
                    tree[v2[q].a]=tree[v2[q].b]+1;
                    v2[q].x=1;
                    empty=1;
                }
            }
        }
//        for(int q=0;q<n;q++)cout<<tree[q]<<" ";
        maxd=-1,maxn=-1;
        for(int q=0;q<n;q++){
            if(tree[q]>maxd){
                maxd=tree[q];
                maxn=q;
            }
        }
        printf("%d\n",maxd);
		
    }
}