Mai intai trebuie sa te autentifici.
Cod sursa(job #1774907)
Utilizator | Data | 9 octombrie 2016 16:37:29 | |
---|---|---|---|
Problema | Componente tare conexe | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 1.5 kb |
#include<fstream>
#include<vector>
#define NMax 100005
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int N,M,k,K;
int Use[NMax],UseT[NMax];
int O[NMax];
vector <int> V[NMax];
vector <int> VT[NMax];
vector <int> CTC[NMax];
void Read()
{
fin>>N>>M;
for(int i = 1 ; i <= M ; ++i)
{
int a,b; fin>>a>>b;
V[a].push_back(b);
VT[b].push_back(a);
}
}
void DFS(int nod)
{
Use[nod] = 1;
for(int i = 0 ; i < (int) V[nod].size() ; ++i)
{
int Vecin = V[nod][i];
if(!Use[Vecin])
{
DFS(Vecin);
}
}
O[++k] = nod;
}
void DFST(int nod)
{
Use[nod] = 0;
CTC[K].push_back(nod);
for(int i = 0 ; i < (int)VT[nod].size() ; ++i)
{
int Vecin = VT[nod][i];
if(Use[Vecin] == 1)
{
DFST(Vecin);
}
}
}
void Solve()
{
for(int i = 1 ; i <= N ; ++i)
{
if(!Use[i])
{
DFS(i);
}
}
for(int i = N ; i >= 1 ; i--)
{
if(Use[O[i]] == 1)
{
K++;
DFST(O[i]);
}
}
}
void Print()
{
fout<<K<<"\n";
for(int i = 1 ; i <= K ; ++i)
{
for(int j = 0 ; j < (int) CTC[i].size() ; ++j)
fout<<CTC[i][j]<<" ";
fout<<"\n";
}
}
int main()
{
Read();
Solve();
Print();
fin.close();
fout.close();
return 0;
}