随笔-141  评论-9  文章-3  trackbacks-0

第一问, 枚举地拿掉每个点u,看能否连通(dfs 到n),能连通的就是必需经过的点,对于点u 进行DFS,看会不会重复经过第一问中已经访问过的点,若都没有经过,则该u点符合第二问。

/*
ID: lorelei3
TASK: race3
LANG: C++
*/


#include 
<fstream>
#include 
<memory.h>

using namespace std;

const int MAX = 55;

ifstream fin(
"race3.in");
ofstream fout(
"race3.out");

int map[MAX][MAX];
int visited[MAX], ans1[MAX], ans2[MAX], cnt1, cnt2, n;

void input(){
    
int i=0in=0;
    
while(fin>>in && in!=-2){
        
int t=in;
        
int c = ++map[i][0];
        map[i][c]
=t;
        
        
while(fin>>&& t!=-2){
            
int c = ++map[i][0];
            map[i][c]
=t;
        }

        i
++;
    }

    fin
>>in;
    n
=i;
}


bool dfs1(int u){
    
if(u==n)
        
return true;

    
for(int i=1; i<=map[u][0]; ++i){
        
int v = map[u][i];
        
if(visited[v]==0){
            visited[v]
=1;
            
if(dfs1(v))
                
return true;
        }

    }

    
return false;
}


bool rep;
void dfs2(int u){
    
if(rep)
        
return;
    
if(visited[u]==2)
        
return;

    visited[u]
=2;
    
for(int i=1; i<=map[u][0]; ++i){
        
int v = map[u][i];
        
if(visited[v]==1){
            rep
=true;
            
return;
        }

        dfs2(v);
    }

}


void solve(){
    
for(int i=1; i<n; ++i){
        memset(visited, 
0sizeof(visited));
        visited[i]
=1;
        visited[
0]=1;
        
if(!dfs1(0)){
            ans1[cnt1
++= i;
            rep 
= false;
            dfs2(i);
            
if(rep == false)
                ans2[cnt2
++= i;
        }

    }

}


void output(){
    
int i;
    fout
<<cnt1;

    
if(cnt1!=0){
        fout
<<" ";
        
for(i=0; i<cnt1-1++i)
            fout
<<ans1[i]<<" ";
        fout
<<ans1[cnt1-1];
    }

    fout
<<endl;

    fout
<<cnt2;
    
if(cnt2!=0){
        fout
<<" ";
        
for(i=0; i<cnt2-1++i)
            fout
<<ans2[i]<<" ";
        fout
<<ans2[cnt2-1];
    }

    fout
<<endl;
}


int main(){

    input();

    solve();

    output();

    
return 0;
}
posted on 2011-01-29 20:01 小阮 阅读(354) 评论(0)  编辑 收藏 引用 所属分类: USACO

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理