我知道了,是图可能不连通的原因吧
by _RedForest @ 2019-02-12 16:44:49
继续求助,还是WA了
by _RedForest @ 2019-02-12 16:53:27
```cpp
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
const int inf=20007;
vector <int> v[inf];
int n,m,tim=0,low[inf],dfn[inf];
bool is_cut[inf];
int fa[inf],cnt=0;
template <typename _TP>
inline void read(_TP &X){
char ch;int w;X=0;
while(!isdigit(ch)){w=ch=='-';ch=getchar();}
while(isdigit(ch)){X=(X<<1)+(X<<3)+(ch^48);ch=getchar();}
X=w?-X:X;
}
inline void input(){
scanf("%d%d",&n,&m);
register int x,y;
for(int i=1;i<=m;++i){
read(x);read(y);
v[x].push_back(y);
v[y].push_back(x);
}
}
void tarjan(int s,int f){
fa[s]=f; //记录dfs树上的每一个节点的父亲
dfn[s]=low[s]=tim++;
for(int i=0;i<v[s].size();i++){
int nxt=v[s][i];
if(dfn[nxt]==-1){
tarjan(nxt,s);
low[s]=min(low[s],low[nxt]);
}
else if(f!=nxt) //如果nxt是s的fa那么就是重边,一定不是桥
low[s]=min(low[s],dfn[nxt]); //dfn[k]可能不等于low[k]所以不能代替!!!
}
}
inline void count(int s){
int rootson=0;
tarjan(s,0);
for(int i=2;i<=n;i++){ //因为是从1节点开始生成的dfs树所以1点必定是根要遍历根的所有子树
int nxt=fa[i];
if(nxt==s)
rootson++;
else if(low[i]>dfn[nxt]){
is_cut[nxt]=true; //割点的条件,这里等于和大于等于都可以
cnt++;
}
}
if(rootson>=2){
is_cut[s]=true;
cnt++;
}
}
inline void INIT(){
memset(dfn,-1,sizeof(dfn));
memset(fa,0,sizeof(fa));
memset(low,-1,sizeof(low));
memset(is_cut,false,sizeof(is_cut));
}
inline void PRINT(){
cout<<cnt<<"\n";
for(int i=1;i<=n;i++)
if(is_cut[i])cout<<i<<"\n";
return;
}
int main(){
INIT();
input();
for(int i=1;i<=n;i++){
if(dfn[i]==-1)count(i);
}
PRINT();
return 0;
}
```
by _RedForest @ 2019-02-12 16:53:49
大槪是我count枚举那里错了,好像必须要边tarjan边处理cut数组
by _RedForest @ 2019-02-12 17:13:35
90分求助
by _RedForest @ 2019-02-12 18:27:24
```cpp
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
const int inf=20007;
vector <int> v[inf];
int n,m,tim=0,low[inf],dfn[inf];
bool is_cut[inf];
int fa[inf],cnt=0;
template <typename _TP>
inline void read(_TP &X){
char ch;int w;X=0;
while(!isdigit(ch)){w=ch=='-';ch=getchar();}
while(isdigit(ch)){X=(X<<1)+(X<<3)+(ch^48);ch=getchar();}
X=w?-X:X;
}
inline void input(){
read(n);read(m);
register int x,y;
for(int i=1;i<=m;++i){
read(x);read(y);
v[x].push_back(y);
v[y].push_back(x);
}
}
void tarjan(int s,int f){
fa[s]=f; //记录dfs树上的每一个节点的父亲
dfn[s]=low[s]=tim++;
for(int i=0;i<v[s].size();i++){
int nxt=v[s][i];
if(dfn[nxt]==-1){
tarjan(nxt,s);
low[s]=min(low[s],low[nxt]);
}
else if(f!=nxt) //如果nxt是s的fa那么就是重边,一定不是桥
low[s]=min(low[s],dfn[nxt]); //dfn[k]可能不等于low[k]所以不能代替!!!
}
}
inline void count(int s){ //这里枚举的时候会算重所以cnt不可靠
int rootson=0;
tarjan(s,0);
for(int i=2;i<=n;i++){ //因为是从1节点开始生成的dfs树所以1点必定是根要遍历根的所有子树
int nxt=fa[i];
if(nxt==s)
rootson++;
else if(low[i]>dfn[nxt])
is_cut[nxt]=true; //割点的条件,这里等于和大于等于都可以
}
if(rootson>=2)
is_cut[s]=true;
}
inline void INIT(){
memset(dfn,-1,sizeof(dfn));
memset(fa,0,sizeof(fa));
memset(low,-1,sizeof(low));
memset(is_cut,false,sizeof(is_cut));
}
inline void PRINT(){
cout<<cnt<<"\n";
for(int i=1;i<=n;i++)
if(is_cut[i])cout<<i<<" ";
return;
}
int main(){
INIT();
input();
for(int i=1;i<=n;i++)
if(dfn[i]==-1)count(i);
for(int i=1;i<=n;i++)
if(is_cut[i])cnt++;
PRINT();
return 0;
}
```
by _RedForest @ 2019-02-12 18:27:38