84分求解QwQ
查看原帖
84分求解QwQ
288716
lzqy_楼主2020/5/17 15:40
#include <bits/stdc++.h>
using namespace std;
int ret[200001],in[200001],len[200001],inde;
vector<int>v[200001];
bool k[200001],ans[200001];
int n,m,child,root,sum;
void Tarjan(int chi)
{
  inde++;
  k[chi]=1;
  in[chi]=inde,ret[chi]=inde;
  for(int w,i=0; i<len[chi]; i++)
  {
    w=v[chi][i];
    if(in[w]==0)
    {
      Tarjan(w);
      if(chi==root)
        child++;
      else
      {
        ret[chi]=min(ret[chi],ret[w]);
        if(in[chi]<=ret[w]&&ans[chi]==0)
          ans[chi]=1,sum++;
      }
    }
    else
      ret[chi]=min(ret[chi],in[w]);
  }
  if(chi==root&&child>=2&&ans[chi]==0)
    ans[chi]=1,sum++;
}
int main()
{
  int x,y;
  cin>>n>>m;
  while(m--)
  {
    cin>>x>>y;
    len[x]++,len[y]++;
    v[x].push_back(y),v[y].push_back(x);
  }
  for(int i=1; i<=n; i++)
    if(k[i]==0)
      root=i,Tarjan(i);
  cout<<sum<<endl;
  for(int i=1; i<=n; i++)
    if(ans[i])
      cout<<i<<" ";
  return 0;
}
2020/5/17 15:40
加载中...