省赛冲刺(5)

拓扑排序

拓扑排序：对有向无回路图进行排序，以期找到一个线性序列，这个线性序列在生活正可以表示某些事情完成的相应顺序。 如果说所求的图有回路的话，则不可能找到这个序列。 P3243 [HNOI2015]菜肴制作 之前贴过代码，再整理下思路，非常巧妙。 1.在满足限制条件下，菜肴的顺序编号小的要尽可能先做 2.我们要标记所有会放在标号小菜肴前面制作的大菜肴，又要通过所有编号小的菜肴从而找到大菜肴，因此可想到编号小的向编号大的建边； 3.如果用数组从小的开始记录，则无法临时储存编号大的菜肴，因此想到可用一个优先队列，将未被标记的所有菜肴放进去，若有限制条件，则找到放在后面。 4.最后逆序输出数组值，即为答案。

P1197 [JSOI2008]星球大战 这道题寒假都做过一遍了，可能隔得时间有点久，想思路还是想了一会儿。 思路： 1.假设要摧毁的星球已全被摧毁，剩下的星球相连可形成几个连通块； 2.再已从后往前的顺序每次修复一个星球，再依次连接和这个星球相连的点，加入到联通块中； 3.由于边的关系较多，为方便查找，用邻接表存储多个信息。

#include 
#define endl '\n'
using namespace std;
const int N=1e6+5;
int n,m,k,head[N],cnt,f[N],p[N],tol;
bool vis[N];
struct node
{
    int from,to,nxt;
}e[N];
void add(int u,int v)    
{
    e[++cnt].from=u;      //再存储一下from
    e[cnt].to=v;
    e[cnt].nxt=head[u];
    head[u]=cnt;
}
int r_find(int r)
{
    if(f[r]==r) return r;
    f[r]=r_find(f[r]);
    return f[r];
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    for(int i=0;iu>>v;
        add(u,v);add(v,u);
    }
    cin>>k;
    for(int i=1;i>p[i];
        vis[p[i]]=1;
    }
    tol=n-k;
    for(int i=1;i=1;i--)
    {
        int u=p[i];tol++;
        vis[u]=0;
        for(int j=head[u];j!=-1;j=e[j].nxt)
        {
            int fx=r_find(u),fy=r_find(e[j].to);
            if(!vis[e[j].to]&&fx!=fy)
                tol--,f[fx]=fy;
        }
        p[i]=tol;
    }
    for(int i=1;i