Pagini recente » Cod sursa (job #2942935) | Cod sursa (job #1077661) | Cod sursa (job #2451583) | Cod sursa (job #670449) | Cod sursa (job #825268)
Cod sursa(job #825268)
#include<fstream>
#include<vector>
#define nmax 100008
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
int N, M, nr, comp_conexe;
vector <int> CTC[nmax], G[nmax], Gt[nmax];
bool see[nmax];
int ord[nmax];
void read()
{
f>>N>>M;
for(int i=1;i<=M;i++)
{
int x, y;
f>>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()
{
g<<comp_conexe<<'\n';
for(int i=1;i<=comp_conexe;i++)
{
for(int j=0;j<CTC[i].size();j++)
g<<CTC[i][j]<<" ";
g<<'\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();
return 0;
}