Pagini recente » Cod sursa (job #1679514) | Cod sursa (job #434485) | Cod sursa (job #642976) | Cod sursa (job #1739943) | Cod sursa (job #1441044)
#include <iostream>
#include <fstream>
#include <vector>
#include <bitset>
#define MAXIM 100005
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
vector<int> gg[MAXIM], gt[MAXIM], ctc[MAXIM/2];
int stack[MAXIM], varf, nrc;
bitset <MAXIM> vizitat;
void dfs(int nod)
{
vizitat[nod]=1;
for( int i=0; i<gg[MAXIM].size();i++)
if(vizitat[gg[nod][i]]==0)
dfs(gg[nod][i]);
stack[++varf]=nod;
}
void dfss(int nod)
{
vizitat[nod]=0;
ctc[nrc].push_back(nod);
for(int i=0; i<gt[nod].size();i++)
if(vizitat[gt[nod][i]]==1)
dfs(gt[nod][i]);
}
int main()
{
int n,m, i,x,y;
f>>n>>m;
for(i=1;i<=m;i++)
{
f>>x>>y;
gg[x].push_back(y);
gt[y].push_back(x);
}
for(i=1;i<=n;i++)
if(vizitat[i]==0)
dfs(i);
for(i=n; i>=1;i--)
if(vizitat[stack[i]]==1)
{
nrc++;
dfss(stack[i]);
}
g<<nrc;
for(i=1;i<=nrc;i++)
{
for(int j=0;j<ctc[i].size();j++)
g<<ctc[i][j];
g<<"\n";
}
return 0;
}