1311.cpp

ZOJ 动态规划算法题目入门与提高 源代码

#include<iostream>
#include<fstream>
#include<vector>
#include<string>
#include<sstream>
using namespace std;
void run(vector<vector<int> > & vec,int n,vector<int> & use,int & t,int deep,int p){
	 int i,j;
	 //cout<<deep<<" "<<p<<endl;
	 if(deep==1){
		 for(i=1;i<=n;i++){
             if(vec[i].size()&&use[i]==0){
			   t+=1;
			   use[i]=1;
               for(j=0;j<vec[i].size();j++){
                  if(use[vec[i][j]]==0){
                     use[vec[i][j]]=1;
				     run(vec,n,use,t,deep+1,vec[i][j]);
				  }
			   }
			 }
		 }
	 }
	 else{
		 for(j=0;j<vec[p].size();j++){
                  if(use[vec[p][j]]==0){
                     use[vec[p][j]]=1;
				     run(vec,n,use,t,deep+1,vec[p][j]);
				  }
		 }
	 }
}
int main(){
	//ifstream cin("in.txt");
    int f,t,c=1,i,j,n;
	string s;
	while(getline(cin,s)&&s!="0"){
        istringstream ns(s);
		ns>>n;
        vector<vector<int> > vec(n+1); vector<int> temp;
		while(getline(cin,s)&&s!="0"){
            istringstream is(s);
			is>>f;
			while(is>>t){
               vec[f].push_back(t); vec[t].push_back(f);
			}
		}
		f=0;
		for(i=1;i<=n;i++){
            if(vec[i].size()==0) continue;
			t=0;
		    temp=vec[i];
			vec[i].clear();
			vector<int> use(n+1,0);
			use[i]=use[0]=1;
			run(vec,n,use,t,1,0);
			vec[i]=temp;
			//cout<<t<<endl;
			if(t>=2){
               f+=1;
			}
		}
		cout<<f<<endl;
	}
}