Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<iostream>
- #include<cstdio>
- #include<cstring>
- #include<vector>
- using namespace std;
- #define si(n) scanf("%d",&n)
- #define MAX 10005
- vector<int>graph[MAX];
- bool vis[MAX],arti_point[MAX];
- int time,disc[MAX],low[MAX];
- void dfs(int now,int prev){
- vis[now]=true;
- disc[now]=low[now]=time++;
- int child=0;
- for(int i=0;i<graph[now].size();i++){
- int to=graph[now][i];
- if(to==prev)
- continue;
- if(vis[to])
- low[now]=min(low[now],disc[to]);
- else{
- dfs(to,now);
- low[now]=min(low[now],low[to]);
- if(low[to]>=disc[now] && prev != -1){
- //now is articulation point
- arti_point[now]=true;
- }
- child++;
- }
- }
- if(prev == -1 && child>1){
- //now is articulation point
- arti_point[now]=true;
- }
- }
- int main()
- {
- int i,j,n,m;
- freopen("input.txt","r",stdin);
- si(n);si(m);
- for(i=0;i<m;i++){
- int u,v;
- si(u);si(v);
- graph[u].push_back(v);
- graph[v].push_back(u);
- }
- memset(arti_point,false,sizeof(arti_point));
- memset(vis,false,sizeof(vis));
- for(i=0;i<n;i++){
- if(!vis[i])
- dfs(i,-1);
- }
- int ans=0;
- for(i=0;i<=n;i++)
- if(arti_point[i])
- ans++,cout<<i<<' ';
- cout<<endl;
- cout<<ans<<endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement