Cod sursa(job #1334896)

Utilizator t_@lexAlexandru Toma t_@lex Data 4 februarie 2015 19:16:11
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
# include <fstream>
# include <vector>
# include <stack>
# define DIM 100001
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
int n,m,i,d,k,a[DIM],b[DIM];
vector<int> v[DIM],c[DIM];
stack<int> s;
bool p[DIM];
void read()
{
    int x,y;
    f>>n>>m;
    for(i=1;i<=m;i++)
         {
          f>>x>>y;
          v[x].push_back(y);
         }
}
void Tarjan(int x)
{
    int i,n=v[x].size();
    s.push(x);
    p[x]=1;
    a[x]=b[x]=++d;
    for(i=0;i<n;i++)
        {
         if(!b[v[x][i]])
             Tarjan(v[x][i]);
         if(p[v[x][i]]&&b[v[x][i]]<b[x])
             b[x]=b[v[x][i]];
        }
    if(a[x]==b[x])
        {
         k++;
         do
          {
           n=s.top();
           s.pop();
           p[n]=0;
           c[k].push_back(n);
          }
         while(n!=x);
        }
}
void write()
{
    int j;
    g<<k<<'\n';
    for(i=1;i<=k;i++)
        {
         d=c[i].size();
         for(j=0;j<d;j++)
              g<<c[i][j]<<" ";
         g<<'\n';
        }
}
int main()
{
    read();
    for(i=1;i<=n;i++)
         if(!a[i])
            Tarjan(i);
    write();
    f.close();
    g.close();
    return 0;
}