1 条题解

  • -27
    @ 2023-8-19 14:28:47
    #include<bits/stdc++.h>
    using namespace std;
    int n,m;
    vector<int>a[100005],g[100005];
    stack<int> st;
    int h[100005],dfn[100005],low[100005],f[100005],times,cnt,fa[100005];
    vector<int>b[100005];
    void dfs(int u){
    	dfn[u]=low[u]=++times;
    	h[u]=1;st.push(u);
    	for(int i=0;i<a[u].size();i++){
    		int v=a[u][i];
    		if(dfn[v]==0){
    			dfs(v);
    			low[u]=min(low[u],low[v]);
    		}else if(h[v]==1)low[u]=min(low[u],dfn[v]);
    	}
    	if(low[u]==dfn[u]){
    		if(st.top()!=u)cnt++;
    		while(st.top()!=u){
    			f[st.top()]=cnt;
    			b[cnt].push_back(st.top());
    			h[st.top()]=0;
    			st.pop();
    		}
    		f[st.top()]=cnt;
    		b[cnt].push_back(st.top());
    		h[st.top()]=0;
    		st.pop();
    	}
    }
    int mian(){
    	cin>>n>>m;
    	for(int i=1;i<=m;i++){
    		int u,v;
    		cin>>u>>v;
    		a[u].push_back(v);
    	}
    	for(int i=1;i<=n;i++){
    		dfs(i);
    	}
    	dfs(1);
    	cout<<cnt;
    	return 0;
    }
    

    信息

    ID
    485
    时间
    1000ms
    内存
    256MiB
    难度
    3
    标签
    递交数
    398
    已通过
    75
    上传者