Pagini recente » Cod sursa (job #624707) | Cod sursa (job #1966611) | Cod sursa (job #303279) | Cod sursa (job #2707509) | Cod sursa (job #2928623)
#include <iostream>
#include <vector>
#include <fstream>
#include <stack>
using namespace std;
int n, nr_comp_conex;
vector <vector <int>> solutie;
vector <vector <int>> ad_1;
vector <vector <int>> ad_2;
vector <int> vizitat;
stack <int> st;
ifstream f("ctc.in");
ofstream g("ctc.out");
void afisare()
{
g<<nr_comp_conex<<"\n";
for( long long int i=1; i <= nr_comp_conex ; i++)
{
for(auto v: solutie[i])
{
g<< v <<" ";
}
g<<"\n";
}
}
void dfs_1(int nod)
{
for(auto i=0; i < ad_1[nod].size();i++)
{
if(vizitat[ad_1[nod][i]]==0)
{
vizitat[ad_1[nod][i]]=1;
dfs_1(ad_1[nod][i]);
}
}
st.push(nod);
}
void dfs_2(int nod)
{
vizitat[nod] = 2;
solutie[nr_comp_conex].push_back(nod);
for( auto i = 0 ;i < ad_2[nod].size(); i++)
{
if(vizitat[ad_2[nod][i]] == 1)
{
dfs_2(ad_2[nod][i]);
}
}
}
creare_lista(int m)
{
for(int i=1;i <= m ; i++)
{ int a,b;
f>>a>>b;
ad_1[a].push_back(b);
ad_2[b].push_back(a);
}
}
int main()
{
int m,nod,i;
f>>n>>m;
solutie.resize(n+1);
vizitat.resize(n+1,0);
ad_1.resize(n+1);
ad_2.resize(n+1);
creare_lista(m);
for(int i = 1; i <= n ; i++)
{
if(vizitat[i] == 0)
{
vizitat[i]=1;
dfs_1(i);
}
}
while(st.size() > 0)
{
nod = st.top();
st.pop();
if(vizitat[nod]==1)
{
nr_comp_conex++;
dfs_2(nod);
}
}
afisare();
return 0;
}