卧薪尝胆,厚积薄发。
新年的毒瘤
Date: Sat Oct 27 07:46:31 CST 2018 In Category: NoCategory

Description:

给一张无向图,问图中有哪些点删掉它和它相连的边后图变成了一棵树。
$1\leqslant n\leqslant 10^5$

Solution:

最后变成了一棵树相当于最后剩下了一个有 $n-2$ 条边的连通图,所以所有度数 $=m-(n-2)$ 的非割点都是满足条件的。

Code:


#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<stack>
#include<vector>
#include<cctype>
#include<cstring>
using namespace std;
int n,m;
#define MAXN 100010
struct edge
{
int to,nxt;
}e[MAXN << 1];
int edgenum = 0;
int lin[MAXN] = {0};
int deg[MAXN];
void add(int a,int b)
{
++deg[a];++deg[b];
++edgenum;e[edgenum].to = b;e[edgenum].nxt = lin[a];lin[a] = edgenum;
++edgenum;e[edgenum].to = a;e[edgenum].nxt = lin[b];lin[b] = edgenum;
return;
}
int dfn[MAXN],low[MAXN],tot = 0;
stack<int> s;
int root;
bool cut[MAXN];
void tarjan(int k)
{
dfn[k] = low[k] = ++tot;
s.push(k);
int flag = 0;
for(int i = lin[k];i != 0;i = e[i].nxt)
{
if(dfn[e[i].to] == 0)
{
tarjan(e[i].to);
low[k] = min(low[k],low[e[i].to]);
if(low[e[i].to] >= dfn[k])
{
++flag;
if(k != root || flag > 1)cut[k] = true;
}
}
else
{
low[k] = min(low[k],dfn[e[i].to]);
}
}
return;
}
int ans = 0;
vector<int> res;
int main()
{
scanf("%d%d",&n,&m);
int a,b;
for(int i = 1;i <= m;++i)
{
scanf("%d%d",&a,&b);
add(a,b);
}
for(int i = 1;i <= n;++i)
{
if(dfn[i] == 0)
{
root = i;
tarjan(i);
}
}
for(int i = 1;i <= n;++i)
{
if(!cut[i] && deg[i] == m - (n - 2))
{
++ans;
res.push_back(i);
}
}
cout << ans << endl;
for(int i = 0;i < res.size();++i)
{
printf("%d ",res[i]);
}
cout << endl;
return 0;
}
Copyright © 2020 wjh15101051
ღゝ◡╹)ノ♡