Pagini recente » Cod sursa (job #690169) | Cod sursa (job #792667) | Cod sursa (job #1292575) | Cod sursa (job #3173350) | Cod sursa (job #943061)
Cod sursa(job #943061)
#include<fstream>
#include<vector>
#include<stack>
#define lmax 100001
using namespace std;
vector <int> vecin[lmax], vecin_2[lmax], v[lmax];
int k, n;
int parcurs1[lmax];
int parcurs2[lmax];
stack<int> s;
ofstream fout("ctc.out");
void df1(int nod)
{
parcurs1[nod] = 1;
vector<int> :: iterator it;
for(it = vecin[nod].begin(); it < vecin[nod].end(); it++)
{
if(parcurs1[vecin[nod][*it]] == 0)
df1(vecin[nod][*it]);
}
s.push(nod);
}
void df2(int nod)
{
v[k].push_back(nod);
parcurs2[nod] = 1;
vector<int> :: iterator it;
for(it = vecin_2[nod].begin(); it < vecin_2[nod].end(); it++)
{
if(parcurs2[vecin_2[nod][*it]] == 0)
df2(vecin_2[nod][*it]);
}
}
void kosaraju()
{
for(int i = 1; i <= n; i++)
if(parcurs1[i] == 0)
df1(i);
while(!s.empty())
{
if(parcurs2[s.top()] == 0)
{
k++;
df2(s.top());
}
s.pop();
}
}
void citire()
{
ifstream fin("ctc.in");
int m, x, y, i;
fin >> n >> m;
for(i = 1; i <= m; i++)
{
fin >> x >> y;
vecin[x].push_back(y);
vecin_2[y].push_back(x);
}
}
void afisare()
{
vector<int> :: iterator it;
fout << k << "\n";
for(int i = 1; i <= k; i++)
{
for(it = v[i].begin(); it < v[i].end(); it++)
fout << v[i][*it] << " ";
fout << "\n";
}
}
int main()
{
citire();
kosaraju();
afisare();
return 0;
}