大家好,又见面了,我是全栈君。
现场赛手速三题,这题一直没写。
直接暴力,注意点只有一个!单向建边,从小点到大点。
1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 using namespace std; 5 struct edge 6 { 7 int to; 8 int next; 9 }E[1011]; 10 int head[111]; 11 bool e[111][111]; 12 int tot; 13 int N,S,M,ans; 14 void addedge(int a,int b) 15 { 16 E[tot].to = a; 17 E[tot].next = head[b]; 18 head[b] = tot++; 19 } 20 int V[20]; 21 int sv = 0; 22 bool check(int t) 23 { 24 for (int i = 1; i<=sv;i++) 25 { 26 if (!e[V[i]][t]) return false; 27 } 28 return true; 29 } 30 void dfs(int u) 31 { 32 if (sv==S) 33 { 34 ans++; 35 return; 36 } 37 for (int i = head[u] ; i!=-1;i = E[i].next) 38 { 39 int v = E[i].to; 40 if (check(v)) 41 { 42 V[++sv] = v; 43 dfs(v); 44 sv--; 45 } 46 } 47 } 48 int main() 49 { 50 int T; 51 cin >> T; 52 while (T--) 53 { 54 cin >> N >> M >>S; 55 memset(head,-1,sizeof(head)); 56 memset(e,false,sizeof(e)); 57 tot = 0; 58 for (int i= 1; i<=M; i++) 59 { 60 int a,b; 61 scanf("%d%d",&a,&b); 62 addedge(min(a,b),max(a,b)); 63 e[a][b] = true; 64 e[b][a] = true; 65 } 66 ans=0; 67 for (int i = 1; i<=N; i++) 68 { 69 sv = 0; 70 V[++sv] = i; 71 dfs(i); 72 } 73 cout <<ans <<endl; 74 } 75 }
View Code
转载于:https://www.cnblogs.com/HITLJR/p/6607769.html
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/108604.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...