蓝桥杯历届试题-网络寻路 （C++代码）

解题思路:
    链表大法好（注意，本题解并非原创）

原题解链接：https://blog.csdn.net/u010126535/article/details/19998143

    利用链表的自动扩张性质，每一次输入相连接的路径时候两端都进行输入设置。
参考代码:

#include<bits/stdc++.h>
using namespace std;
const int maxn=100005;
int n,m,ans=0;
struct node{
 int data;
 struct node *next;
}tab[maxn];
int vis[maxn];
void add(int a,int b){
 struct node *q =&tab[a];
 while(q->next!=NULL){
  q=q->next;
 }
 struct node *s;
 s=(struct node*)malloc(sizeof(struct node));
 q->next=s;
 s->data=b;
 s->next=NULL;
}
void dfs(int x,int n,int s){
 vis[x]=1;
 struct node *q=&tab[x];
 if(n>=3){
  ans++;
  return ;
 }
 while((q=q->next)!=NULL){
  int w=q->data;
  if(vis[w]!=1||(w==s&&n==2)){
   dfs(w,n+1,s);
   if(w!=s){
    vis[w]=0;
   }
  }
 }
}
int main(){
 cin>>n>>m;
 for(int i=1;i<=n;i++){
  tab[i].data=i;
  tab[i].next=NULL;
 }
 while(m--){
  int x,y;
  cin>>x>>y;
  add(x,y);
  add(y,x);
 }
 for(int i=1;i<=n;i++){
  memset(vis,0,sizeof(vis));
  dfs(i,0,i);
 }
 cout<<ans<<endl;
 return 0;
}