本文共 2509 字,大约阅读时间需要 8 分钟。
131 22 33 11 3
9
/*思路:题目意思是一个n个点的无向图,给你n+1条边,求有多少种删除办法,使得图还能连通至少删除一条边我的思路是,n个点,要连通,至少是n-1条边,所以最多删除2条,枚举每一条边,删除求连通若可以,+1,尝试枚举下一条边被删,看能不能继续连通 */ /* 超时 没用邻接表 复杂度O(n*n)的递归 */ /*#include#include using namespace std;const int N=100+5;struct Node{ int x,y;}node[N];int check; int map[N][N]; //记录边数 用int可以累加 bool book[N];int n;void dfs(int now){ //深搜 book[now]=1; check++; for(int i=1;i<=n;i++){ //这里时间复杂度n^2 if(book[i]) continue; if(map[now][i]>0) dfs(i); }}int main(){ int t,re; cin>>t; while(t--){ re=0; cin>>n; memset(map,0,sizeof(map)); for(int i=0;i >node[i].x>>node[i].y; map[node[i].x][node[i].y]++; map[node[i].y][node[i].x]++; } for(int i=0;i #include #include #include using namespace std;const int N=100+5;struct Node{ int x,y;}node[N];vector ve[N];int map[N][N]; //记录边数 用int可以累加 bool book[N];int check; int n;void dfs(int now){ //深搜 book[now]=1; check++; for(int i=0;i 0) dfs(ve[now][i]); }}//用一个全局变量减少判断,复杂度减少O(n)//inline bool check(){ //求连通 // for(int i=1;i<=n;i++)// if(!book[i])// return false; // return true;//}int main(){ int t,re; scanf("%d",&t); while(t--){ re=0; scanf("%d",&n); memset(map,0,sizeof(map)); for(int i=1;i<=n;i++){ ve[i].clear(); } for(int i=0;i >node[i].x>>node[i].y; ve[node[i].x].push_back(node[i].y); ve[node[i].y].push_back(node[i].x); map[node[i].x][node[i].y]++; map[node[i].y][node[i].x]++; } memset(book,0,sizeof(book)); check=0; dfs(1); if(check!=n){ printf("0\n"); continue; } for(int i=0;i
转载地址:http://ydmvi.baihongyu.com/