【基础练习】【强连通tarjan】codevs2822 爱在心中题解

àì夳堔傛蜴生んèń 2022-08-09 09:47 12阅读 0赞

题目描述 Description

“每个人都拥有一个梦，即使彼此不相同，能够与你分享，无论失败成功都会感动。爱因为在心中，平凡而不平庸，世界就像迷宫，却又让我们此刻相逢Our Home。”

在爱的国度里有N个人，在他们的心中都有着一个爱的名单，上面记载着他所爱的人（不会出现自爱的情况）。爱是具有传递性的，即如果A爱B，B爱C，则A也爱C。  
如果有这样一部分人，他们彼此都相爱，则他们就超越了一切的限制，用集体的爱化身成为一个爱心天使。  
现在，我们想知道在这个爱的国度里会出现多少爱心天使。而且，如果某个爱心天使被其他所有人或爱心天使所爱则请输出这个爱心天使是由哪些人构成的，否则输出-1。

输入描述 Input Description

第1行，两个数N、M，代表爱的国度里有N个人，爱的关系有M条。  
第2到第M+1行，每行两个数A、B，代表A爱B。

输出描述 Output Description

第1行，一个数，代表爱的国度里有多少爱心天使。  
第2行，如果某个爱心天使被其他所有人和爱心天使所爱则请输出这个爱心天使是由哪些人构成的（从小到大排序），否则输出-1。

样例输入 Sample Input

样例输入1：

6 7  
1 2  
2 3  
3 2  
4 2  
4 5  
5 6  
6 4

样例输入2：

3 3  
1 2  
2 1  
2 3

样例输出 Sample Output

样例输出1：

2  
2 3

样例输出2：

1  
\-1

数据范围及提示 Data Size & Hint

各个测试点1s

虽然题面很肉麻，但这道题目也并不是特别难

首先毫无疑问tarjan一遍。接下来就是找所有点都指向的一个scc，但这个scc又不能是一个点。怎么办呢？其实，我们只要找出度为0的强连通分量就好。因为如果这个所有强连通分量都指向的scc有出度的话，那么一定会形成一个更大的强连通分量。如果出度为0的点大于一个，那么无解，因为第二个出度为0的点没有指向第一个，不满足所有scc都指向第一个点的条件。

因此我们的目标很清晰：统计出度，找出出度为0的强连通分量，不止一个则输出-1

那么如果出度为0的是一个点怎么办呢？我们可以在出栈时同时统计这个强连通分量中有几个点，如果不止一个，那么爱心天使个数++；否则，把他的出度赋值为无穷大。

既然已经赋值为无穷大了，最后寻找的时候就有可能出现找不到的情况，这时now==-1，输出-1

程序如下：

//codevs2822 爱在心中 tarjan
    //copyright by ametake
    //task:首先做一个强连通分量 然后对于每个scc统计出度 出度为0必定是 如果两个以上则无解
    #include
       
        
    #include
        
         
    #include
         
          
    #include
          
           
    using namespace std;
    
    const int maxn=1000+10;
    const int maxm=10000+10;
    int n,m;
    int head[maxn],to[maxm],next[maxm],et=0;
    int sta[maxn],dfn[maxn],low[maxn],stp=0,dep=0;
    bool ins[maxn];
    int tot,angel=0;
    vector
           
             v[maxn]; int out[maxn],inwhich[maxn]; inline int read() { int a=0,f=1; char ch=getchar(); while (ch<'0'||ch>'9') { if (ch=='-') f=-1; ch=getchar(); } while (ch>='0'&&ch<='9') { a=a*10+ch-'0'; ch=getchar(); } a*=f; return a; } inline void add(int x,int y) { et++; to[et]=y; next[et]=head[x]; head[x]=et; //out[x]++;这是不可以的，因为强连通分量中的边应当被忽略 } void init() { n=read(); m=read(); int x,y; for (int i=1;i<=m;i++) { x=read(); y=read(); add(x,y); } return; } void tarjan(int k) { dfn[k]=low[k]=dep++; ins[k]=true; sta[++stp]=k;//最好写成++stp 否则容易出现下标和元素个数不对应的情况 出栈时会有麻烦 for (int i=head[k];i!=0;i=next[i]) { if (!dfn[to[i]]) { tarjan(to[i]); low[k]=min(low[k],low[to[i]]); } else if (ins[to[i]]) { low[k]=min(low[k],low[to[i]]); } } if (dfn[k]==low[k]) { tot++; int cnt=0; int j; do { j=sta[stp--]; cnt++; ins[j]=false; inwhich[j]=tot; v[tot].push_back(j); }while (j!=k); if (cnt!=1) { angel++; } else out[tot]=0x3f3f3f; } return; } int main() { freopen("1.txt","r",stdin); freopen("2.txt","w",stdout); init(); for (int i=1;i<=n;i++) { if (!dfn[i]) tarjan(i); } printf("%d\n",angel); for (int i=1;i<=n;i++) { for (int j=head[i];j!=0;j=next[j])//j写成i啦！！！又犯低级错误！ { if (inwhich[i]!=inwhich[to[j]]) { out[inwhich[i]]++; } } } //for (int i=1;i<=n;i++) printf("%d\n",inwhich[i]); int cnt=0,now=-1; for (int i=1;i<=tot;i++) { if (out[i]==0) { now=i; cnt++; if (cnt>1) { printf("-1\n"); return 0; } } } if (now==-1) { printf("-1\n"); return 0; } sort(v[now].begin(),v[now].end()); for (int i=0;i

`——天阶夜色凉如水，卧看牵牛织女星。`