X 国的一个网络使用若干条线路连接若干个节点。节点间的通信是双向的。某重要数据包，为了安全起见，必须恰好被转发两次到达目的地。该包可能在任意一个节点产生，我们需要知道该网络中一共有多少种不同的转发路径。
源地址和目标地址可以相同，但中间节点必须不同。
如下图所示的网络。
1 -> 2 -> 3 -> 1 是允许的
1 -> 2 -> 1 -> 2 或者 1 -> 2 -> 3 -> 2 都是非法的。
输入格式输入数据的第一行为两个整数N M，分别表示节点个数和连接线路的条数(1<=N<=10000; 0<=M<=100000)。
接下去有M行，每行为两个整数 u 和 v，表示节点u 和 v 联通(1<=u,v<=N , u!=v)。
输入数据保证任意两点最多只有一条边连接，并且没有自己连自己的边，即不存在重边和自环。
输出格式 输出一个整数，表示满足要求的路径条数。 样例输入1 3 3 1 2 2 3 1 3 样例输出1 6 样例输入2 4 4 1 2 2 3 3 1 1 4 样例输出2 10 简单dfs #include <iostream> #include <cstdio> #include <cstring> #include <queue> #include <cmath> #include <algorithm> #include <vector> #include <map> #include <string> #include <stack> using namespace std; typedef long long ll; #define PI 3.1415926535897932 #define E 2.718281828459045 #define INF 0x3f3f3f3f #define mod 100000007 const int M=1005; int n,m; int cnt; int sx,sy,sz; //int g[M][M]; int pa[M*10],rankk[M]; int head[M*6],vis[M*100]; int dis[M*100]; ll prime[M*1000]; bool isprime[M*1000]; int lowcost[M],closet[M]; char st1[5050],st2[5050]; int len[M*6]; typedef pair<int ,int> ac; //vector<int> g[M*10]; int dp[M]; int has[10500]; int month[13]= {0,31,59,90,120,151,181,212,243,273,304,334,0}; int dir[8][2]= {{0,1},{0,-1},{-1,0},{1,0},{1,1},{1,-1},{-1,1},{-1,-1}}; void getpri() { ll i; int j; cnt=0; memset(isprime,false,sizeof(isprime)); for(i=2; i<1000000LL; i++) { if(!isprime[i])prime[cnt++]=i; for(j=0; j<cnt&&prime[j]*i<1000000LL; j++) { isprime[i*prime[j]]=1; if(i%prime[j]==0)break; } } } struct node { int v,w; node(int vv,int ww) { v=vv; w=ww; } }; vector<int> g[M*100]; void dfs(int u,int sum,int st)//u,当前点，sum转发次数，st记录起点 { if(sum>2) { cnt++; return ; } //vis[u]=1; for(int i=0; i<g[st].size(); i++) { int v=g[st][i]; //if(!vis[v]||(v==st&&sum==2)) if(v!=u) { dfs(st,sum+1,v); //if(v!=st) //vis[v]=0; } } } int main() { int i,j,k,t; int u,v,w; scanf("%d%d",&n,&m); for(i=0; i<m; i++) { scanf("%d%d",&u,&v); g[u].push_back(v); g[v].push_back(u); } for(i=1; i<=n; i++) { //memset(vis,0,sizeof(vis)); dfs(i,0,i); } printf("%d\n",cnt); return 0; }