捉Firrel
by zcs_accept @ 2024-01-23 10:28:48
@[Firrel](/user/530570) ```cpp
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<vector>
using namespace std;
int n,m;
vector<int> mp[2000005];
bool dix[2000005];
int dfn[2000005],low[2000005];
int tot,ans;
void Tarjan(int x,int fa,int root){
int len = mp[x].size();
dfn[x] = low[x] = ++tot;
int flag = 0;
for(int i = 0;i < len;i++){
int y = mp[x][i];
if(!dfn[y]){
Tarjan(y,x,root);
low[x] = min(low[x],low[y]);
if(low[y] >= dfn[x]) {
flag++;
if(flag >= 2 || x != root){
if(!dix[x]) ans++;
dix[x] = 1;
}
}
}
else if(y != fa) low[x] = min(low[x],dfn[y]);
}
return ;
}
int main(){
scanf("%d%d",&n,&m);
for(int i = 1;i <= m;i++){
int u,v;
scanf("%d%d",&u,&v);
mp[u].push_back(v);
mp[v].push_back(u);
}
for(int i = 1;i <= n;i++){
if(!dfn[i]) Tarjan(i,0,i);
}
printf("%d\n",ans);
for(int i = 1;i <= n;i++){
if(dix[i]) printf("%d ",i);
}
return 0;
}
```
判断割点错了
by xiao__xiao @ 2024-01-25 16:36:56
@[Firrel](/user/530570)
```cpp
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<vector>
using namespace std;
int n,m;
vector<int> mp[2000005];
bool dix[2000005];
int dfn[2000005],low[2000005];
int tot,ans;
void Tarjan(int x,int fa,int root){
int len = mp[x].size();
dfn[x] = low[x] = ++tot;
int flag = 0;
for(int i = 0;i < len;i++){
int y = mp[x][i];
if(!dfn[y]){
Tarjan(y,x,root);
low[x] = min(low[x],low[y]);
if(low[y] >= dfn[x]) {
flag++;
if(flag >= 2 || x != root){
if(!dix[x]) ans++;
dix[x] = 1;
}
}
}
else if(y != fa) low[x] = min(low[x],dfn[y]);
}
return ;
}
int main(){
scanf("%d%d",&n,&m);
for(int i = 1;i <= m;i++){
int u,v;
scanf("%d%d",&u,&v);
mp[u].push_back(v);
mp[v].push_back(u);
}
for(int i = 1;i <= n;i++){
if(!dfn[i]) Tarjan(i,0,i);
}
printf("%d\n",ans);
for(int i = 1;i <= n;i++){
if(dix[i]) printf("%d ",i);
}
return 0;
}
```
判断割点错了
by xiao__xiao @ 2024-01-25 16:37:24
谢谢，之前自己改过了
by Firrel @ 2024-03-21 16:51:27
但是依然关注捏
by Firrel @ 2024-03-21 16:51:44
自己改的AC代码
```cpp
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<vector>
#include<queue>
using namespace std;
int n,m;
vector<int> mp[2000005];
bool dix[2000005];
int dfn[2000005],low[2000005];
int tot,ans;
void Tarjan(int x,int fa,int root){
int len = mp[x].size();
dfn[x] = low[x] = ++tot;
int flag = 0;
for(int i = 0;i < len;i++){
int y = mp[x][i];
if(!dfn[y]){
Tarjan(y,x,root);
low[x] = min(low[x],low[y]);
if(low[y] >= dfn[x]) {
flag++;
if(flag >= 2 || x != root){
if(dix[x] == 0) ans++;
dix[x] = 1;
}
}
}
else if(y != fa) low[x] = min(low[x],dfn[y]);
}
return ;
}
bool vis[2000005];
void bfs(int sta){
queue<int> q;
q.push(sta);
vis[sta] = 1;
while(!q.empty)
return ;
}
int main(){
scanf("%d%d",&n,&m);
for(int i = 1;i <= m;i++){
int u,v;
scanf("%d%d",&u,&v);
mp[u].push_back(v);
mp[v].push_back(u);
}
for(int i = 1;i <= n;i++) if(!dfn[i]) Tarjan(i,0,i);
printf("%d\n",ans);
for(int i = 1;i <= n;i++){
if(!vis[i]){
bfs(i);
}
}
return 0;
}
```
by Firrel @ 2024-03-21 16:52:47