偶是用DFS判连通并且检查出度和入度

#include "stdio.h"
#include "stdlib.h"
#include "string.h"
#include "math.h"

long long inc[26],outc[26],cn,n;
int conn[26][26],visited[26];
char str[2000];

void dfs(int i){
    int j;
    visited[i]=1;
    for (j=0;j<26;j++){
        if (!visited[j]&&conn[i][j])dfs(j);
    }
}

int chkConn(){
    int i;
    for (i=0;i<26;i++){
        if (!visited[i]&&(inc[i]+outc[i]))return 0;
    }
    return 1;
}

int chkDegree(){
    int count=0,i;
    for (i=0;i<26;i++){
        int t=abs(inc[i]-outc[i]);
        if (t>1)return 0;
        else if(t==1)count++;
    }
    return (count==2)||(count==0);
}

int main(){
    int i,j,c1,c2;
    long long k;
    #ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    scanf("%d",&cn);
    while(cn--){
        scanf("%d",&n);
        for (i=0;i<26;i++){
            inc[i]=outc[i]=visited[i]=0;
            for (j=0;j<26;j++){
                conn[i][j]=0;
            }
        }
        for (k=0;k<n;k++){
            scanf("%s",str);
            c1=str[0]-'a';
            c2=str[strlen(str)-1]-'a';
            inc[c2]++;
            outc[c1]++;
            conn[c1][c2]=1;
        }
        for (i=0;i<26;i++){
            if (outc[i]){
                dfs(i);
                break;
            }
        }
        if (!chkConn()||!chkDegree()){
            printf("The door cannot be opened.\n");
        }
        else{
            printf("Ordering is possible.\n");
        }
    }
    
    return 0;
}

• 这是无向图啊,判连通的时候有问题呢 (0) yiyiyi4321 2005-10-30 22:31:15