Pagini recente » Cod sursa (job #771020) | Cod sursa (job #965004) | Cod sursa (job #2823627) | Cod sursa (job #2592220) | Cod sursa (job #2444994)
#include <bits/stdc++.h>
#define NMAX 100001
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
vector <int> v[NMAX], a[NMAX], b[NMAX];
int viz[NMAX], x, y, n, t, comp, i, j;
stack <int> S;
void dfs(int k)
{
viz[k] = 1;
for(int i = 0; i < v[k].size(); ++ i)
{
int x = v[k][i];
if(!viz[x]) dfs(x);
}
S.push(k);
}
void dfs1(int k)
{
viz[k] = 2;
b[comp].push_back(k);
for(int i = 0; i < a[k].size(); ++ i)
{
int x = a[k][i];
if(viz[x] == 1) dfs1(x);
}
}
int main()
{
f >> n >> t;
while(t --)
{
f >> x >> y;
v[x].push_back(y);
a[y].push_back(x);
}
for(i = 1; i <= n; ++ i)
if(!viz[i]) dfs(i);
while(!S.empty())
{
int x = S.top();
if(viz[x] == 1)
{
comp ++;
dfs1(x);
}
S.pop();
}
g << comp << "\n";
for(i = 1; i <= comp; ++ i)
{
for(j = 0; j < b[i].size(); ++ j)
g << b[i][j] << " ";
g << "\n";
}
return 0;
}