Pagini recente » Cod sursa (job #2234870) | Cod sursa (job #2303353) | Cod sursa (job #1710956) | Istoria paginii runda/oji2011x | Cod sursa (job #2498738)
#include <iostream>
#include <fstream>
#include <vector>
#include<stack>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
vector <int> L1[100001];
vector <int> L2[100001];
vector < vector <int> > sol;
vector <int> vec;
stack <int> stiva;
vector <int> comp;
bool viz1[100001], viz2[100001];
int n, m, x, y, nr;
/// pas 1 citire si bagare in L1 si L2
void citire()
{
f>>n>>m;
for(int i=1; i<=m; i++)
{
f>>x>>y;
L1[x].push_back(y);
L2[y].push_back(x);
}
}
/// pas 2 scriere DFS1 si DFS2 una pe L1 si una pe L2
void DFS1(int k)
{
viz1[k]=1;
for(int i=0; i<L1[k].size(); i++)
{
int nod=L1[k][i];
if(viz1[nod]==0)
DFS1(nod);
}
stiva.push(k);
}
void DFS2(int k)
{
viz2[k]=1;
for(int i=0; i<L2[k].size(); i++)
{
int nod=L2[k][i];
if(viz2[nod]==0)
DFS2(nod);
}
comp.push_back(k);
}
/// pas 3 functia rezolva care va fi alcatuita din 2 bucatele
/// prima bucatica e sa parcurgi ca pe componentele conexe normale cu DFS1
/// a doua parte explic eu
void rezolva()
{
for(int j=1; j<=n; j++)
if(viz1[j]==0)
DFS1(j);
while(!stiva.empty())
{
int t = stiva.top();
stiva.pop();
comp.clear();
if(viz2[t]==0)
{
// cout << vec[t] << " ";
DFS2(t);
sol.push_back(comp);
}
}
}
/// pas 4
/// scrie main ()
/// afisarea ?? la ce -> da-ti seama din enuntul problemei ce trebuie afisat
/// si declarati o matrice sau vectori sau ceva care sa salveze chestiile
void afisare()
{
g<<sol.size()<<endl;
for(int l=0; l<sol.size(); l++)
{
for(int l2=0; l2<sol[l].size(); l2++)
g<<sol[l][l2]<<" ";
g<<endl;
}
}
/// pas 5
/// intelegem
int main()
{
citire();
rezolva();
afisare();
return 0;
}