Cod sursa(job #2084309)

Utilizator andrei13Paval Andrei andrei13 Data 8 decembrie 2017 22:08:11
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.5 kb
#include <iostream>
#include <fstream>
#include <stack>
#include <list>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
stack <int> s;
list <int> :: iterator it,sf;
int n,m,T,index[32000],low[32001];
list <int> lista[32001];
bool st[32001];
void sc(int v);
void tarjan()
{
    for(int i=1;i<=n;i++)
        if(!index[i])
        sc(i);
}
int k=1;
int nr;
void sc(int v)
{
    index[v]=k;
    low[v]=k;
    k++;
    s.push(v);
    st[v]=true;
    sf=lista[v].end();
    it=lista[v].begin();
    while(it!=sf)
    {
        int w=*it;
        if(!index[w])
        {
            sc(w);
            low[v]=min(low[v],low[w]);
        }
        else if(st[w])
            low[v]=min(low[v],index[w]);
        ++it;
    }
    if(low[v]==index[v])
    {
        int w;
        do
        {
            w=s.top();
            s.pop();
            st[w]=0;
            index[w]=index[v];

        }
        while(w!=v);
    }
}
int main()
{
f>>n>>m;
int i,j;
while(m--)
{f>>i>>j;
 lista[i].push_back(j);}
 tarjan();

for(int i=1;i<=n;i++)
    if(index[i]>0)
    {
    nr++;
    for(int j=i+1;j<=n;j++)
        if(index[i]==index[j])
         index[j]=(-1)*index[i];
    index[i]=(-1)*index[i];
    }
g<<nr<<endl;
for(int i=1;i<=n;i++)
    if(index[i]<0)
    {g<<i<<' ';
    for(int j=i+1;j<=n;j++)
        if(index[i]==index[j])
         {g<<j<<' ';
         index[j]=0;
         }
    index[i]=0;
    g<<endl;
    }
    return 0;
}