Cod sursa(job #1265595)

Utilizator t_@lexAlexandru Toma t_@lex Data 17 noiembrie 2014 14:55:03
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
# include <cstdio>
# include <vector>
using namespace std;
vector <int> a[100001],b[100001];
vector<pair<int,int> > v;
int n,m,i,x,y,k;
bool c[100001],d[100001],t[100001];
void DFS1(int x)
{
    if(!c[x]&&!t[x])
    {
    c[x]=1;
    int i,m;
    m=a[x].size();
    for(i=0;i<m;i++)
         DFS1(a[x][i]);
    }
}
void DFS2(int x)
{
    if(!d[x]&&!t[x])
    {
    d[x]=1;
    if(c[x])
    {v.push_back(make_pair(x,k));t[x]=1;}
    int i,m;
    m=b[x].size();
    for(i=0;i<m;i++)
         DFS2(b[x][i]);
    }
}
void ini()
{
    int i;
    for(i=1;i<=n;i++)
          c[i]=d[i]=0;
}
int main()
{
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {
     scanf("%d%d",&x,&y);
     a[x].push_back(y);
     b[y].push_back(x);
    }
    for(i=1;i<=n;i++)
    {
        if(!t[i]){
        ini();
        k++;
        //v.push_back(make_pair(i,k));
        DFS1(i);
        DFS2(i);}
    }
    printf("%d\n",k);
    printf("%d ",v[0].first);
    for(i=1;i<v.size();i++)
          if(v[i].second==v[i-1].second)
              printf("%d ",v[i].first);
          else
            printf("\n%d ",v[i].first);
    return 0;
}