Pagini recente » Cod sursa (job #503279) | Cod sursa (job #2444231) | Cod sursa (job #348136) | Cod sursa (job #1709972) | Cod sursa (job #2166485)
#include <iostream>
#include <fstream>
#include <stack>
#include <vector>
using namespace std;
int n,viz[100005];
vector<int> v[100005],v2[100005];
vector< vector<int> > ctc;
stack<int> stiva;
void DFS1(int x)
{
viz[x]=1;
for (size_t i=0; i<v[x].size(); i++)
{
if (viz[v[x][i]]==0)
DFS1(v[x][i]);
}
stiva.push(x);
}
void DFS2(int x, vector<int> &comp)
{
viz[x]=1;
comp.emplace_back(x);
for (size_t i=0; i<v2[x].size(); i++)
{
if (viz[v2[x][i]]==0)
DFS2(v2[x][i],comp);
}
}
int main()
{
int i,x,y,m,j,nr=0;
ifstream f("ctc.in");
ofstream g("ctc.out");
f>>n>>m;
for (i=1; i<=m; i++)
{
f>>x>>y;
v[x].emplace_back(y);
v2[y].emplace_back(x);
}
for (i=1; i<=n; i++)
{
if (viz[i]==0)
DFS1(i);
}
for (i=1; i<=n; i++)
viz[i]=0;
while (stiva.empty()==0)
{
x=stiva.top();
stiva.pop();
if (viz[x]==0)
{
vector<int> comp;
DFS2(x,comp);
ctc.push_back(comp);
nr++;
}
}
g<<nr<<'\n';
for (i=0;i<nr;i++)
{
for (j=0;j<ctc[i].size();j++)
g<<ctc[i][j]<<" ";
g<<'\n';
}
return 0;
}