Pagini recente » Cod sursa (job #1811805) | Cod sursa (job #1938449) | Cod sursa (job #2539937) | Cod sursa (job #2666984) | Cod sursa (job #806130)
Cod sursa(job #806130)
#include<fstream>
#include<vector>
#define nmax 100008
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int N, M, nr, comp_conexe;
vector <int> CTC[1000], G[nmax], Gt[nmax];
bool see[nmax];
int ord[nmax];
void read()
{
fin >>N>> M;
for(int i = 1; i <= M; i++)
{
int x, y;
fin >> x>> y;
G[x].push_back(y);
Gt[y].push_back(x);
}
}
void DFS(int x)
{
see[x] = true;
for(int i = 0; i < G[x].size(); i++)
{
if(see[G[x][i]] == false)
DFS(G[x][i]);
}
ord[++nr] = x;
}
void DFS2(int x)
{
see[x] = false;
CTC[comp_conexe].push_back(x);
for(int i = 0; i < Gt[x].size(); i++)
{
if(see[Gt[x][i]])
DFS2(Gt[x][i]);
}
}
void display()
{
fout << comp_conexe <<'\n';
for(int i = 1; i <= comp_conexe; i++){
for(int j = 0 ;j < CTC[i].size(); j++)
fout << CTC[i][j] <<" ";
fout << '\n';
}
}
int main()
{
read();
for(int i = 1; i <= N; i++)
if(see[i] == false)
DFS(i);
for(int i = N; i > 0 ;i--)
{
if(see[ord[i]] == true)
{
comp_conexe++;
DFS2(ord[i]);
}
}
display();
fin.close();
return 0;
}