Pagini recente » Cod sursa (job #1495418) | Cod sursa (job #2299784) | Cod sursa (job #2868008) | Cod sursa (job #2206029) | Cod sursa (job #2928997)
#include <bits/stdc++.h>
#include <vector>
#include <stack>
#include <fstream>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n,m,x,y,i,s,nr,p=1;
vector<int> la[100001],lat[100001];
vector<vector<int>> solutie;
vector <int> comp;
stack <int> stiva;
void DFS(int nod, int viz[])
{
viz[nod] = 1;
for(i=0; i<la[nod].size(); i++)
{
int vecin = la[nod][i];
if(viz[vecin]==0)
DFS(vecin,viz);
}
stiva.push(nod);
}
void DFST(int nod, int viz[])
{
viz[nod] = 1;
comp.push_back(nod);
for(i=0; i<lat[nod].size(); i++)
{
int vecin = lat[nod][i];
if(viz[vecin]==0)
DFST(vecin, viz);
}
}
int main()
{
int viz[100];
fin>>n>>m;
for(i=1; i<=n; i++)
viz[i]=0;
for(i=1; i<=m; i++)
{
fin>>x>>y;
la[x].push_back(y);
lat[y].push_back(x);
}
for(i=1; i<=n; i++)
sort(la[i].begin(), la[i].end());
for(i=1; i<=n; i++)
if(viz[i]==0)
DFS(i,viz);
//for(i=1; i<=n; i++)
//cout<<viz[i]<<" ";
//cout<<endl;
for(i=1; i<=n; i++)
viz[i]=0;
while(!stiva.empty())
{
int v = stiva.top();
stiva.pop();
if(viz[v]==0)
{
nr++;
DFST(v,viz);
solutie.push_back(comp);
comp.clear();
}
}
fout<<nr<<endl;
for(i=0; i<solutie.size(); i++)
{for(int j=0; j<solutie[i].size(); j++)
fout<<solutie[i][j]<<" ";
fout<<endl;
}
fout.close();
}