hdu5950 dfs

    xiaoxiao2021-12-15  6

    #include<iostream> #include<algorithm> #include<cstring> #include<cmath> #include<cstdio> #include<string> #include<set> #include<map> #include<queue> #include<vector> #include<stack> using namespace std; #define ll long long #define cl(a,b) memset(a,b,sizeof(a)) #define N 50005 #define MAXN 10005 const int inf=2147483647; #define lson i<<1,l,mid #define rson i<<1|1,mid+1,r int n,m,s,ans; vector<int>ve[105]; int g[105][105]; void dfs(int v,int *vis,int sum) { if(sum==s){ ans++; return; } for(int j=0;j<ve[v].size();j++){ int flag=1; int u=ve[v][j]; for(int i=1;i<=sum;i++) { if(g[u][vis[i]]==0) { flag=0; break; } } if(flag){ sum++; vis[sum]=v; dfs(u,vis,sum); vis[sum]=0; sum--; } } } int main() { int t,test=0,x,y; scanf("%d",&t); while(t--) { scanf("%d%d%d",&n,&m,&s); for(int i=0;i<=n;i++)ve[i].clear(); ans=0; int vis[105]; cl(g,0); for(int i=0;i<m;i++){ scanf("%d%d",&x,&y); if(x>y)swap(x,y); ve[x].push_back(y); g[x][y]=1; g[y][x]=1; } for(int i=1;i<=n;i++){ vis[1]=i; dfs(i,vis,1); } printf("%d\n",ans); } return 0; }
    转载请注明原文地址: https://ju.6miu.com/read-1000273.html

    最新回复(0)