POJ2553

时间:2023-03-08 22:25:30

题意:很难懂!但是大体意思就是求有向图中从一个节点出发到达的点也能反向到达该节点的点。如a能到{b1,b2.....bx}这些点,而这些点也能到a,则a为要求的点。题目是求出所有的这种点。

对图进行缩点,缩点后出度为0的点(强连通分量)所包含的点就是答案。原因,自己思考一下.....

 #include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<stack>
#include<vector>
using namespace std;
const int maxn=;
const int maxm=;
int n,m;
struct edge
{
int u,v,next;
}e[maxm],ee[maxm];
int head[maxn],js,headd[maxn],jss;
int dfsn[maxn],low[maxn],visx,sshu;
int belong[maxn],ss[maxn];
stack<int>st;
bool ins[maxn];
int chudu[maxn];
vector<int>bl[maxn];
vector<int>ans;
void init()
{
memset(head,,sizeof(head));
memset(e,,sizeof(e));
js=;
memset(headd,,sizeof(headd));
memset(ee,,sizeof(ee));
jss=;
memset(dfsn,,sizeof(dfsn));
memset(low,,sizeof(low));
visx=sshu=;
memset(belong,,sizeof(belong));
memset(ss,,sizeof(ss));
while(!st.empty())st.pop();
memset(ins,,sizeof(ins));
memset(chudu,,sizeof(chudu));
ans.resize();
for(int i=;i<maxn;i++)bl[i].resize();
}
void addage(int u,int v,edge e[],int head[],int &js)
{
e[++js].u=u;e[js].v=v;
e[js].next=head[u];head[u]=js;
}
void tarjan(int u)
{
low[u]=dfsn[u]=++visx;
st.push(u);
ins[u]=;
for(int i=head[u];i;i=e[i].next)
{
int v=e[i].v;
if(dfsn[v]==)
{
tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(ins[v] && low[u]>dfsn[v]) low[u]=dfsn[v];
}
if(low[u]==dfsn[u])
{
sshu++;
int tp;
do{
tp=st.top();
st.pop();
ins[tp]=;
bl[sshu].push_back(tp);
belong[tp]=sshu;
ss[sshu]++;
}while(tp!=u);
}
}
void addd(int x)
{
for(int i=;i<bl[x].size();i++)
{
int y=bl[x][i];
ans.push_back(y);
}
} int main()
{
while(scanf("%d%d",&n,&m)==)
{
init();
for(int u,v,i=;i<m;i++)
{
scanf("%d%d",&u,&v);
addage(u,v,e,head,js);
}
for(int i=;i<=n;i++)
if(dfsn[i]==)tarjan(i);
for(int i=;i<=m;i++)
{
int u=e[i].u,v=e[i].v;
if(belong[u]!=belong[v])
{
addage(belong[u],belong[v],ee,headd,jss);
chudu[belong[u]]++;
}
}
for(int i=;i<=sshu;i++)
if(chudu[i]==)addd(i);
sort(ans.begin(),ans.end());
for(int i=;i<ans.size();i++)printf("%d ",ans[i]);
printf("\n");
} return ;
}