Cod sursa(job #1914708)

Utilizator radu.leonardoThe Doctor radu.leonardo Data 8 martie 2017 18:11:01
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.37 kb
#include <bits/stdc++.h>
#define buff_size 3666013
char buff[buff_size];
int pos=0;
char outBuff[buff_size];
int outPtr;
FILE*f=freopen("ctc.in","r",stdin);
FILE*g=freopen("ctc.out","w",stdout);
using namespace std;

int n,m;
bitset<100001> visited;
int ST[100001],k=0;
vector <int> G[100001];
vector <int> G_reversed[100001];

int components_number=0;
vector<int> components[100001];

inline void read(int &nr)
{
    while(!isdigit(buff[pos])) if(++pos == buff_size) fread(buff,  1,buff_size, stdin), pos = 0;
    nr = 0;
    while(isdigit(buff[pos]))
    {
        nr = (nr<<1)+(nr<<3)+ buff[pos] - 48;
        if(++pos == buff_size) fread(buff, 1, buff_size, stdin), pos = 0;
    }
}

inline void putChar(const char &C)
{
    outBuff[outPtr++] = C;
    if (outPtr == buff_size) {
        fwrite(outBuff, 1, buff_size, stdout);
        outPtr = 0;
    }
}

inline  void write(int X)
{
    static char digs[10];
    int n = 0, q;
    do {
        q = X / 10;
        digs[n++] = X - (q << 1) - (q << 3) + 48;

        X = q;
    } while (X);
    while (n--) {
        putChar(digs[n]);
    }

}

void read_data()
{
    int x,y;
    read(n);read(m);
    for(int i=1;i<=m;i++)
    {
        read(x);read(y);
        G[x].push_back(y);
        G_reversed[y].push_back(x);
    }
}

void DFS(int node)
{
    visited[node]=1;
    for(size_t i=0;i<G[node].size();i++)
            {
                int next_node=G[node][i];
                if(visited[next_node]==0) DFS(next_node);
            }
    ST[++k]=node;
}

void DFS2(int node)
{
    visited[node]=0;
    for(size_t i=0;i<G_reversed[node].size();i++)
            {
                int next_node=G_reversed[node][i];
                if(visited[next_node]==1) DFS2(next_node);
            }
    components[components_number].push_back(node);
}

void kosaraju()
{
    for(int i=1;i<=n;i++)   if(visited[i]==0)     DFS(i);
    for(int i=k;i>=1; i--)  if(visited[ST[i]]==1) components_number++,DFS2(ST[i]);
}

void write_result()
{
    write(components_number);putChar('\n');
    for(int i=1;i<=components_number;i++)
        {
            for(int j=0;j<components[i].size();j++)   write(components[i][j]),putChar(' ');
            putChar('\n');
        }
    fwrite(outBuff, 1, buff_size, stdout);
}

int main()
{
    read_data();
    kosaraju();
    write_result();
}