网站研发公司,张家港外贸网站建设,哈尔滨免费网站制作,管理软件有哪几种图论day60|108.冗余连接#xff08;卡码网#xff09;、109.冗余连接II#xff08;卡码网#xff09;【并查集 摧毁信心的一题#xff0c;胆小的走开#xff01;】 108.冗余连接#xff08;卡码网#xff09;109.冗余连接II#xff08;卡码网#xff09;【并查集 摧毁… 图论day60|108.冗余连接卡码网、109.冗余连接II卡码网【并查集 摧毁信心的一题胆小的走开】 108.冗余连接卡码网109.冗余连接II卡码网【并查集 摧毁信心的一题胆小的走开】 108.冗余连接卡码网
题目描述
有一个图它是一棵树他是拥有 n 个节点节点编号1到n和 n - 1 条边的连通无环无向图其实就是一个线形图如图 现在在这棵树上的基础上添加一条边依然是n个节点但有n条边使这个图变成了有环图如图 先请你找出冗余边删除后使该图可以重新变成一棵树。
输入描述
第一行包含一个整数 N表示图的节点个数和边的个数。
后续 N 行每行包含两个整数 s 和 t表示图中 s 和 t 之间有一条边。
输出描述
输出一条可以删除的边。如果有多个答案请删除标准输入中最后出现的那条边。
输入示例
3
1 2
2 3
1 3输出示例
1 3提示信息 图中的 1 22 31 3 等三条边在删除后都能使原图变为一棵合法的树。但是 1 3 由于是标准输出里最后出现的那条边所以输出结果为 1 3
数据范围
1 N 1000. #include iostream
#include vector
using namespace std;int n;
vectorint father(1001,0);void init()
{for(int i1;in;i)father[i]i;
}int find(int u)
{return ufather[u]?u:father[u]find(father[u]);
}bool isSame(int u,int v)
{ufind(u);vfind(v);return uv;
}void join(int u,int v)
{ufind(u);vfind(v);if(uv)return;elsefather[v]u;
}int main()
{cinn;init();int s,t;for(int i0;in;i){cinst;if(isSame(s,t)){couts tendl;return 0;}elsejoin(s,t);}
}109.冗余连接II卡码网【并查集 摧毁信心的一题胆小的走开】
题目描述
有一种有向树,该树只有一个根节点所有其他节点都是该根节点的后继。该树除了根节点之外的每一个节点都有且只有一个父节点而根节点没有父节点。有向树拥有 n 个节点和 n - 1 条边。如图 现在有一个有向图有向图是在有向树中的两个没有直接链接的节点中间添加一条有向边。如图 输入一个有向图该图由一个有着 n 个节点(节点编号 从 1 到 n)n 条边请返回一条可以删除的边使得删除该条边之后该有向图可以被当作一颗有向树。
输入描述
第一行输入一个整数 N表示有向图中节点和边的个数。
后续 N 行每行输入两个整数 s 和 t代表这是 s 节点连接并指向 t 节点的单向边
输出描述
输出一条可以删除的边若有多条边可以删除请输出标准输入中最后出现的一条边。
输入示例
3
1 2
1 3
2 3输出示例
2 3提示信息 在删除 2 3 后有向图可以变为一棵合法的有向树所以输出 2 3
数据范围
1 N 1000. #include iostream
#include vector
using namespace std;int n;
vectorint father(1001,0);void init()
{for(int i1;in;i)father[i]i;
}int find(int u)
{return ufather[u]?u:father[u]find(father[u]);
}bool isSame(int u,int v)
{ufind(u);vfind(v);return uv;
}void join(int u,int v)
{ufind(u);vfind(v);if(uv)return;elsefather[v]u;
}bool deleteIsTree(vectorvectorint edges,int x)
{init();for(int i0;in;i){if(ix) continue;if(isSame(edges[i][0],edges[i][1]))return false;elsejoin(edges[i][0],edges[i][1]);}return true;
}void removeEdge(vectorvectorint edges)
{init();for(int i0;in;i){if(isSame(edges[i][0],edges[i][1]))coutedges[i][0] edges[i][1]endl;elsejoin(edges[i][0],edges[i][1]);}
}int main()
{int s,t;cinn;vectorvectorint edges;vectorint inDegree(n1,0);vectorint vec;for(int i0;in;i){cinst;edges.push_back({s,t});inDegree[t];}for(int in-1;i0;i--){if(inDegree[edges[i][1]]2)vec.push_back(i);}if(vec.size()0){if(deleteIsTree(edges,vec[0]))coutedges[vec[0]][0] edges[vec[0]][1]endl;elsecoutedges[vec[1]][0] edges[vec[1]][1]endl;return 0;}removeEdge(edges);
}
